제출 #1022219

#제출 시각아이디문제언어결과실행 시간메모리
1022219hmm789Connecting Supertrees (IOI20_supertrees)C++14
100 / 100
161 ms28240 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; vector<int> grp[1000], grp2[1000]; vector<vector<int>> p; int cnt = 0, n; int pos[1000], pos2[1000]; bool v[1000]; void dfs(int x) { grp[cnt].push_back(x); pos[x] = cnt; v[x] = 1; for(int i = 0; i < n; i++) if(!v[i] && p[x][i] == 1) dfs(i); } void dfs2(int x, int g) { v[x] = 1; grp2[g].push_back(x); pos2[x] = g; for(int i = 0; i < cnt; i++) if(!v[i] && p[grp[x][0]][grp[i][0]] == 2) dfs2(i, g); } int construct(std::vector<std::vector<int>> P) { n = (int)P.size(); vector<vector<int>> ans; for(int i = 0; i < n; i++) { vector<int> v; for(int j = 0; j < n; j++) v.push_back(P[i][j]); p.push_back(v); vector<int> v2; v2.resize(n); ans.push_back(v2); } for(int i = 0; i < n; i++) if(!v[i]) { dfs(i); cnt++; } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(pos[i] != pos[j] && p[i][j] == 1) return 0; if(pos[i] == pos[j] && p[i][j] != 1) return 0; if(p[grp[pos[i]][0]][grp[pos[j]][0]] != p[i][j]) return 0; if(p[i][j] == 3) return 0; } } memset(v, 0, sizeof(v)); int c2 = 0; for(int i = 0; i < cnt; i++) if(!v[i]) dfs2(i, c2++); for(int i = 0; i < c2; i++) { for(int j : grp2[i]) { for(int k : grp2[i]) { if(p[grp[j][0]][grp[k][0]] == 0) return 0; } } } for(int i = 0; i < cnt; i++) { for(int j = 0; j < cnt; j++) { if(pos2[i] != pos2[j] && p[grp[i][0]][grp[j][0]] == 2) return 0; } } for(int i = 0; i < cnt; i++) { for(int j = 1; j < grp[i].size(); j++) { ans[grp[i][0]][grp[i][j]] = ans[grp[i][j]][grp[i][0]] = 1; } } memset(v, 0, sizeof(v)); for(int i = 0; i < cnt; i++) if(!v[i]) { v[i] = 1; int prv = i, cnt2 = 0; for(int j = 0; j < cnt; j++) if(!v[j] && p[grp[i][0]][grp[j][0]] == 2) { ans[grp[prv][0]][grp[j][0]] = ans[grp[j][0]][grp[prv][0]] = 1; v[j] = 1; prv = j; cnt2++; } if(cnt2 == 1) return 0; if(i != prv) ans[grp[prv][0]][grp[i][0]] = ans[grp[i][0]][grp[prv][0]] = 1; } build(ans); return 1; }

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 1; j < grp[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
#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...