10711 | 2024. 04. 10 09:45:50 | szil | Vasútépítés | cpp17 | Elfogadva 100/100 | 52ms | 22656 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1001;
const int MAXM = 200'001;
const int INF = 1e8;
vector<pair<int, int>> g[MAXN];
vector<int> g2[MAXN];
int vis[MAXN], vis2[MAXM], vis3[MAXN];
int nodes, edges, fok[MAXN], ans[MAXN][MAXN], timer = 2, timer2 = INF, st;
void dfs(int u, int p = -1) {
vis[u] = true;
nodes++;
for (auto [v, idx] : g[u]) {
if (v == p) continue;
if (vis2[idx] == 0) {
vis2[idx] = true;
edges++;
}
if (!vis[v]) {
vis2[idx] = 3;
dfs(v, u);
} else {
st = u;
ans[u][v] = ans[v][u] = 1;
}
}
}
vector<int> cyc;
vector<int> res;
void dfs2(int u, int p = -1) {
vis3[u] = true;
cyc.push_back(u);
for (auto [v, idx] : g[u]) {
if (v == p) continue;
if (v == st) {
res = cyc;
}
if (!res.empty()) return;
if (!vis3[v]) {
dfs2(v, u);
}
if (!res.empty()) return;
}
cyc.pop_back();
}
void dfs3(int u) {
vis3[u] = true;
for (auto [v, idx] : g[u]) {
if (!vis3[v]) {
ans[u][v] = ans[v][u] = timer++;
}
}
for (auto [v, idx] : g[u]) {
if (!vis3[v]) {
dfs3(v);
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ans[i][j] = timer2--;
}
}
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
}
for (int i = 1; i <= n; i++) {
if (g[i].empty()) {
cout << "-1\n";
return 0;
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
nodes = edges = 0;
st = i;
dfs(i);
if (edges > nodes) {
cout << "-1\n";
return 0;
}
fill(vis3, vis3+MAXN, false);
cyc.clear(); res.clear();
dfs2(st);
if (edges == nodes && res.empty()) {
throw 1;
}
if (edges == nodes - 1 && !res.empty()) throw 1;
if (res.empty()) {
fill(vis3, vis3+MAXN, false);
dfs3(st);
} else {
for (int i = 1; i < res.size(); i++) {
ans[res[i-1]][res[i]] = ans[res[i]][res[i-1]] = timer++;
}
ans[res[0]][res.back()] = ans[res.back()][res[0]] = timer++;
fill(vis3, vis3+MAXN, false);
for (int u : res) vis3[u] = true;
for (int u : res) {
dfs3(u);
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
cout << ans[i][j] << " ";
}
cout << "\n";
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 2044 KiB | ||||
2 | Elfogadva | 3ms | 2296 KiB | ||||
3 | Elfogadva | 3ms | 3140 KiB | ||||
subtask2 | 40/40 | ||||||
4 | Elfogadva | 50ms | 10300 KiB | ||||
5 | Elfogadva | 50ms | 10296 KiB | ||||
6 | Elfogadva | 52ms | 10644 KiB | ||||
7 | Elfogadva | 52ms | 11132 KiB | ||||
8 | Elfogadva | 50ms | 11224 KiB | ||||
9 | Elfogadva | 52ms | 11048 KiB | ||||
10 | Elfogadva | 52ms | 11244 KiB | ||||
11 | Elfogadva | 3ms | 3124 KiB | ||||
subtask3 | 60/60 | ||||||
12 | Elfogadva | 50ms | 10300 KiB | ||||
13 | Elfogadva | 50ms | 10296 KiB | ||||
14 | Elfogadva | 52ms | 10644 KiB | ||||
15 | Elfogadva | 52ms | 11132 KiB | ||||
16 | Elfogadva | 50ms | 11224 KiB | ||||
17 | Elfogadva | 52ms | 11048 KiB | ||||
18 | Elfogadva | 52ms | 11244 KiB | ||||
19 | Elfogadva | 3ms | 3124 KiB | ||||
20 | Elfogadva | 50ms | 11532 KiB | ||||
21 | Elfogadva | 50ms | 11612 KiB | ||||
22 | Elfogadva | 50ms | 11592 KiB | ||||
23 | Elfogadva | 50ms | 11496 KiB | ||||
24 | Elfogadva | 50ms | 11508 KiB | ||||
25 | Elfogadva | 52ms | 11784 KiB | ||||
26 | Elfogadva | 50ms | 11796 KiB | ||||
27 | Elfogadva | 50ms | 12176 KiB | ||||
28 | Elfogadva | 52ms | 22656 KiB | ||||
29 | Elfogadva | 6ms | 12208 KiB | ||||
30 | Elfogadva | 7ms | 12296 KiB | ||||
31 | Elfogadva | 6ms | 12188 KiB |