This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
int n;
vector<vector<int>> ans;
vector<vector<int>> ord[3005];
int arr[3005][3005];
int par[3005];
vector<int> roads[3005];
int col[3005];
vector<int> checked;
int findpar(int x){
if(x!=par[x]){
int p = findpar(par[x]);
par[x] = p;
}
return par[x];
}
void domerge(int a, int b){
if(findpar(a)!=findpar(b)){
ans.push_back({a,b});
par[findpar(a)] = findpar(b);
roads[a].push_back(b);
roads[b].push_back(a);
}
}
void dfs(int x, int par){
int iscol = x;
bool all=true;
for(int i:checked){
if(arr[x][i]==arr[par][i]){
iscol = col[i];
}
else{
all = false;
}
}
if(all){
col[x] = col[par];
}
else{
col[x] = iscol;
}
checked.push_back(x);
for(int i:roads[x]){
if(i!=par){
dfs(i,x);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
col[0] = 1;
int sub;
cin >> sub;
cin >> n;
for(int i=1;i<=n;i++){
par[i] = i;
for(int j=1;j<=n;j++){
cin >> arr[i][j];
if(i<j){
ord[arr[i][j]].push_back({i,j});
}
}
}
for(int j=1;j<=n;j++){
for(vector<int> i:ord[j]){
domerge(i[0],i[1]);
}
}
dfs(1,0);
for(int i=1;i<=n;i++){
cout << col[i] << " ";
}
cout << "\n";
for(vector<int> i:ans){
cout << i[0] << " " << i[1] << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |