Submission #994867

#TimeUsernameProblemLanguageResultExecution timeMemory
994867Newtonabc슈퍼트리 잇기 (IOI20_supertrees)C++14
100 / 100
197 ms24148 KiB
#include "supertrees.h" #include<bits/stdc++.h> using namespace std; const int N=1e3+10; vector<int> v; int pa[N]; bool cy[N][N]; vector<int> adj[N]; int cnt=0; bool vs[N]; void dfs(int u){ vs[u]=true; cnt++; if(adj[u].size()==1) v.push_back(u); for(int i=0;i<adj[u].size();i++){ if(!vs[adj[u][i]]) dfs(adj[u][i]); } } int root(int x){ if(pa[x]==x) return x; else return pa[x]=root(pa[x]); } int construct(vector<vector<int> > p) { int n = p.size(); vector<vector<int> > answer; for (int i = 0; i < n; i++) { vector<int> row(n,0); answer.push_back(row); } for(int i=0;i<n;i++) pa[i]=i; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(p[i][j]==1 && root(i)!=root(j)){ answer[i][j]=1; answer[j][i]=1; pa[root(i)]=root(j); } if(p[i][j]==3) return 0; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(p[i][j]==0){ if(root(i)==root(j)) return 0; } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int a,b; if(p[i][j]==2){ a=root(i),b=root(j); if(a==b) continue; pa[a]=b; answer[a][b]=1; answer[b][a]=1; adj[a].push_back(b); adj[b].push_back(a); } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(root(i)==root(j) && p[i][j]==0) return 0; } } for(int i=0;i<n;i++){ cnt=0; if(!vs[i]) dfs(i); if(cnt==2) return 0; if(v.empty()) continue; answer[v[0]][v[1]]=1; answer[v[1]][v[0]]=1; v.clear(); } build(answer); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:15:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...