Submission #1081500

#TimeUsernameProblemLanguageResultExecution timeMemory
10815007modyConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
149 ms24148 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> ans; for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); ans.push_back(row); } for(int i = 0; i < n;i++){ if(p[i][i] != 1) return 0; for(int j = i + 1;j < n;j++){ if(p[i][j] != p[j][i] || p[i][j] == 3) return 0; } } vector<bool> vis(n, false); for(int i = 0; i < n;i++){ if(vis[i]) continue; vis[i] = true; vector<int> curr(1, i); for(int j = i + 1; j < n;j++){ if(p[i][j] != 0 && vis[j]) return 0; if(p[i][j] != 0) curr.push_back(j), vis[j] = true; } int m = curr.size(); vector<vector<int>> branches; vector<bool> temp(n, false); for(int a = 0; a < m;a++){ int x = curr[a]; if(temp[x]) continue; vector<int> add; add.push_back(x); for(int b = a+1; b < m;b++){ int y = curr[b]; if(p[x][y] == 1){ add.push_back(y); temp[y] = true; } } branches.push_back(add); } if(branches.size() == 2) return 0; for(vector<int> x : branches){ for(int a : x){ for(int b : x){ if(a == b) continue; if(p[a][b] != 1) return 0; } } for(int a = 0; a < x.size() - 1;a++){ ans[x[a]][x[a+1]] = ans[x[a+1]][x[a]] = 1; } } int szbr = branches.size(); int szcurr = curr.size(); for(int x = 0; x < szbr;x++){ vector<bool> bb(n); for(int a : branches[x]){ bb[a] = true; } for(int a : branches[x]){ for(int b : curr){ if(bb[b]) continue; if(p[a][b] != 2) return 0; } } } for(int j = 1; j < szcurr;j++){ for(int k = 0; k < n;k++){ int a = curr[j]; int b = curr[0]; if(a == k || b == k) continue; bool ok1 = p[a][k] >=1; bool ok2 = p[b][k] >=1; if(ok1 != ok2) return 0; } } for(int x = 0; x < szbr - 1; x++){ ans[branches[x][0]][branches[x+1][0]] = ans[branches[x+1][0]][branches[x][0]] = 1; } if(branches.size() > 1) ans[branches[0][0]][branches[szbr-1][0]] = ans[branches[szbr-1][0]][branches[0][0]] = 1; } build(ans); return 1; }

Compilation message (stderr)

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