제출 #234861

#제출 시각아이디문제언어결과실행 시간메모리
234861aggu_01000101Izlet (COI19_izlet)C++14
18 / 100
2085 ms80796 KiB
#include <bits/stdc++.h> #define int long long #define INF 1000000000000000000 #define mid(l, u) ((l+u)/2) #define rchild(i) (i*2 + 2) #define lchild(i) (i*2 + 1) using namespace std; const int N = 3005; int dist[N][N]; int root[N]; int sz[N]; bool vis[N]; int freq[N]; int col[N]; int curr = 1; int tf = 0; vector<int> adj[N]; int findroot(int i){ if(i!=root[i]) root[i] = findroot(root[i]); return root[i]; } void MERGE(int i, int j){ int r1 = findroot(i); int r2 = findroot(j); if(r1==r2) return; if(sz[r1]>sz[r2]) swap(r1, r2); adj[j].push_back(i); adj[i].push_back(j); root[r1] = r2; sz[r2]+=sz[r1]; } bool dfs1(int i, int p, int prevdist){ if(i<=0) return false; if(!vis[i]) return false; if(freq[col[i]]==0 && prevdist==dist[tf][i]){ col[tf] = col[i]; return true; } bool tr = false; freq[col[i]]++; for(int j: adj[i]){ if(j==p) continue; tr = tr || dfs1(j, i, dist[tf][i]); } freq[col[i]]--; return tr; } int dfs(int i, int p){ tf = i; for(int k = 0;k<=N;k++){ freq[k] = 0; } bool setnew = false; for(int j: adj[i]){ setnew = setnew || dfs1(j, i, 1); } if(!setnew){ col[i] = curr++; } vis[i] = true; for(int j: adj[i]){ if(j==p) continue; dfs(j, i); } } signed main(){ int type; cin>>type; int n; cin>>n; for(int i = 1;i<=n;i++){ root[i] = i; sz[i] = 1; vis[i] = false; for(int j = 1;j<=n;j++){ cin>>dist[i][j]; } } for(int i = 1;i<=n;i++){ for(int j = 1;j<=n;j++){ if(dist[i][j]==1) MERGE(i, j); } } for(int i = 1;i<=n;i++){ for(int j = 1;j<=n;j++){ if(dist[i][j]==2) MERGE(i, j); } } dfs(1, 0); for(int i = 1;i<=n;i++){ cout<<col[i]<<" "; } cout<<endl; for(int i = 1;i<=n;i++){ for(int j: adj[i]){ if(j>i) cout<<i<<" "<<j<<endl; } } return 0; } /* 3 5 1 2 2 2 3 2 1 3 3 2 2 3 1 3 4 2 3 3 1 3 3 2 4 3 1 */ /* 2 4 1 2 3 3 */

컴파일 시 표준 에러 (stderr) 메시지

izlet.cpp: In function 'long long int dfs(long long int, long long int)':
izlet.cpp:65:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
izlet.cpp:51:17: warning: iteration 3005 invokes undefined behavior [-Waggressive-loop-optimizations]
         freq[k] = 0;
         ~~~~~~~~^~~
izlet.cpp:50:20: note: within this loop
     for(int k = 0;k<=N;k++){
                   ~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...