#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
vector<int>no(3003);
vector<int>tree[3003],T[3003];
vector<int>color(3003,-1);
vector<vector<int>>adj(3003,vector<int>(3003));
int F(int x){
if(no[x]==x)return x;
return no[x]=F(no[x]);
}
bool merge(int x,int y){
x=F(x);
y=F(y);
if(x==y)return false;
if(x<y)swap(x,y);
no[x]=y;
return true;
}
int dfs(int x,int pre,int X,set<int>& S){
int cnt=-1;
for(int i=0;i<T[x].size();i++){
int y=T[x][i];
if(y==pre)continue;
bool added=S.insert(color[y]).second;
if(adj[X][y]!=S.size()){
return color[y];
}
else {
cnt=max(dfs(y,x,X,S),cnt);
if(cnt>0)return cnt;
}
if(added)
S.erase(color[y]);
}
return cnt;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("q.gir","r",stdin);
// freopen("q.cik","w",stdout);
int k;
cin>>k;
int n;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>adj[i][j];
}
}
for(int i=0;i<n;i++)no[i]=i;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
if(adj[i][j]==1){
if(merge(i,j)){
tree[i].pb(j);
tree[j].pb(i);
}
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(adj[i][j]==2){
if(merge(i,j)){
tree[i].pb(j);
tree[j].pb(i);
}
}
}
}
color[0]=1;
queue<int>Q;
Q.push(0);
int ind=2;
while(!Q.empty()){
int x=Q.front();
Q.pop();
for(int i=0;i<tree[x].size();i++){
int y=tree[x][i];
if(color[y]<0){
Q.push(y);
T[x].pb(y);
T[y].pb(x);
set<int>S;S.insert(-1);
color[y]=dfs(y,-1,y,S);
if(color[y]==-1)color[y]=ind++;
}
}
}
for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
for(int i=0;i<n;i++){
for(int j=0;j<tree[i].size();j++)if(i<tree[i][j])cout<<i+1<<" "<<tree[i][j]+1<<"\n";
}
}
Compilation message
izlet.cpp: In function 'long long int dfs(long long int, long long int, long long int, std::set<long long int>&)':
izlet.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<T[x].size();i++){
~^~~~~~~~~~~~
izlet.cpp:33:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(adj[X][y]!=S.size()){
izlet.cpp: In function 'int32_t main()':
izlet.cpp:88:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<tree[x].size();i++){
~^~~~~~~~~~~~~~~
izlet.cpp:100:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
^~~
izlet.cpp:100:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
^~~~
izlet.cpp:102:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<tree[i].size();j++)if(i<tree[i][j])cout<<i+1<<" "<<tree[i][j]+1<<"\n";
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
71160 KB |
Output is correct |
| 2 |
Correct |
808 ms |
88808 KB |
Output is correct |
| 3 |
Correct |
890 ms |
88696 KB |
Output is correct |
| 4 |
Correct |
768 ms |
88056 KB |
Output is correct |
| 5 |
Correct |
796 ms |
88540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
723 ms |
86272 KB |
Output is correct |
| 2 |
Correct |
773 ms |
88696 KB |
Output is correct |
| 3 |
Correct |
1595 ms |
102016 KB |
Output is correct |
| 4 |
Correct |
1614 ms |
100524 KB |
Output is correct |
| 5 |
Correct |
759 ms |
89040 KB |
Output is correct |
| 6 |
Correct |
801 ms |
89392 KB |
Output is correct |
| 7 |
Correct |
614 ms |
89960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
71160 KB |
Output is correct |
| 2 |
Correct |
808 ms |
88808 KB |
Output is correct |
| 3 |
Correct |
890 ms |
88696 KB |
Output is correct |
| 4 |
Correct |
768 ms |
88056 KB |
Output is correct |
| 5 |
Correct |
796 ms |
88540 KB |
Output is correct |
| 6 |
Correct |
723 ms |
86272 KB |
Output is correct |
| 7 |
Correct |
773 ms |
88696 KB |
Output is correct |
| 8 |
Correct |
1595 ms |
102016 KB |
Output is correct |
| 9 |
Correct |
1614 ms |
100524 KB |
Output is correct |
| 10 |
Correct |
759 ms |
89040 KB |
Output is correct |
| 11 |
Correct |
801 ms |
89392 KB |
Output is correct |
| 12 |
Correct |
614 ms |
89960 KB |
Output is correct |
| 13 |
Correct |
832 ms |
89420 KB |
Output is correct |
| 14 |
Correct |
1239 ms |
79868 KB |
Output is correct |
| 15 |
Correct |
772 ms |
88888 KB |
Output is correct |
| 16 |
Correct |
899 ms |
84088 KB |
Output is correct |
| 17 |
Correct |
864 ms |
78624 KB |
Output is correct |
| 18 |
Correct |
731 ms |
84996 KB |
Output is correct |
| 19 |
Correct |
880 ms |
84692 KB |
Output is correct |
| 20 |
Correct |
766 ms |
84512 KB |
Output is correct |
| 21 |
Correct |
792 ms |
83960 KB |
Output is correct |
| 22 |
Correct |
793 ms |
83832 KB |
Output is correct |
| 23 |
Correct |
880 ms |
82808 KB |
Output is correct |
| 24 |
Correct |
967 ms |
77044 KB |
Output is correct |
| 25 |
Correct |
732 ms |
82908 KB |
Output is correct |
