#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 3010;
int A[MAXN][MAXN];
bool chk[MAXN];
int cnt[MAXN];
int ans[MAXN], cn;
vector<int> ed[MAXN];
int uni[MAXN];
vector<pii> edges;
int guni(int x) { return uni[x] ? uni[x] = guni(uni[x]) : x; }
void unite(int x, int y) { uni[guni(y)] = guni(x); }
int dfs(int v, int x, int p, int k) {
if(++cnt[ans[x]] == 1) k++;
if(A[v][x] < k) {
cnt[ans[x]]--;
return ans[x];
}
for(auto a : ed[x]) if(a != p) {
int t = dfs(v, a, x, k);
if(t) {
cnt[ans[x]]--;
return t;
}
}
cnt[ans[x]]--;
return 0;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N;
cin >> N;
cin >> N;
for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) cin >> A[i][j];
for(int i = 1; i <= N; i++) for(int j = i + 1; j <= N; j++) if(A[i][j] == 1 && guni(i) != guni(j)) {
edges.emplace_back(i, j);
unite(i, j);
}
vector<int> v = {1};
ans[1] = cn = 1;
chk[1] = true;
while(!v.empty()) {
int x = v.back();
v.pop_back();
for(int i = 1; i <= N; i++) if(A[x][i] == 2 && !chk[i] && guni(i) == i) {
ans[i] = dfs(i, x, 0, 1);
if(!ans[i]) ans[i] = ++cn;
ed[x].push_back(i);
ed[i].push_back(x);
edges.emplace_back(x, i);
chk[i] = true;
v.push_back(i);
}
}
for(int i = 1; i <= N; i++) cout << ans[guni(i)] << " ";
cout << "\n";
for(auto a : edges) cout << a.first << " " << a.second << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
655 ms |
40008 KB |
Output is correct |
| 3 |
Correct |
676 ms |
39832 KB |
Output is correct |
| 4 |
Correct |
634 ms |
39672 KB |
Output is correct |
| 5 |
Correct |
645 ms |
39648 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
649 ms |
39780 KB |
Output is correct |
| 2 |
Correct |
644 ms |
39168 KB |
Output is correct |
| 3 |
Correct |
880 ms |
36628 KB |
Output is correct |
| 4 |
Correct |
907 ms |
36656 KB |
Output is correct |
| 5 |
Correct |
624 ms |
36232 KB |
Output is correct |
| 6 |
Correct |
693 ms |
36252 KB |
Output is correct |
| 7 |
Correct |
512 ms |
30704 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
655 ms |
40008 KB |
Output is correct |
| 3 |
Correct |
676 ms |
39832 KB |
Output is correct |
| 4 |
Correct |
634 ms |
39672 KB |
Output is correct |
| 5 |
Correct |
645 ms |
39648 KB |
Output is correct |
| 6 |
Correct |
649 ms |
39780 KB |
Output is correct |
| 7 |
Correct |
644 ms |
39168 KB |
Output is correct |
| 8 |
Correct |
880 ms |
36628 KB |
Output is correct |
| 9 |
Correct |
907 ms |
36656 KB |
Output is correct |
| 10 |
Correct |
624 ms |
36232 KB |
Output is correct |
| 11 |
Correct |
693 ms |
36252 KB |
Output is correct |
| 12 |
Correct |
512 ms |
30704 KB |
Output is correct |
| 13 |
Correct |
654 ms |
36136 KB |
Output is correct |
| 14 |
Correct |
804 ms |
36276 KB |
Output is correct |
| 15 |
Correct |
627 ms |
36052 KB |
Output is correct |
| 16 |
Correct |
728 ms |
36172 KB |
Output is correct |
| 17 |
Correct |
732 ms |
36120 KB |
Output is correct |
| 18 |
Correct |
693 ms |
36144 KB |
Output is correct |
| 19 |
Correct |
689 ms |
36196 KB |
Output is correct |
| 20 |
Correct |
638 ms |
36128 KB |
Output is correct |
| 21 |
Correct |
649 ms |
36088 KB |
Output is correct |
| 22 |
Correct |
667 ms |
36088 KB |
Output is correct |
| 23 |
Correct |
655 ms |
36088 KB |
Output is correct |
| 24 |
Correct |
731 ms |
35980 KB |
Output is correct |
| 25 |
Correct |
625 ms |
35956 KB |
Output is correct |
