# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
366897 | 2021-02-15T16:33:11 Z | rumen_m | Connecting Supertrees (IOI20_supertrees) | C++17 | 1 ms | 364 KB |
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; const int maxn = 1005; vector <short> g[maxn]; vector <short> ones[maxn]; short id[maxn], ids = 0; bool vis[maxn]; vector <int> groups[maxn]; //short ans[maxn][maxn]; vector <vector <int> > ans; short newids[maxn]; void dfs(int v) { id[v]=ids; int i; for(i=0;i<g[v].size();i++) { if(id[g[v][i]]==0)dfs(g[v][i]); } } void solve(int v) { newids[v] = ids; vis[v] = 1; int i; for(i=0;i<ones[v].size();i++) { if(!vis[ones[v][i]]) { ans[v][ones[v][i]] = 1; solve(ones[v][i]); } } } int construct(std::vector<std::vector<int>> p) { int n = p.size(); ans.resize(n); int i,j,t; for(i=0;i<n;i++) ans[i].resize(n); for(i=0;i<n;i++) for(j=0;j<n;j++) { if(i==j)continue; if(p[i][j]==3)return 0; if(p[i][j]>0) { /* for(t=0;t<n;t++) { if((p[i][t]>0)^(p[j][t]>0)==1)return 0; if(p[i][j]==1) if(p[i][t]==1^p[j][t]==1)return 0; }*/ } if(p[i][j]!=0) { g[i].push_back(j); g[j].push_back(i); } if(p[i][j]==1) { ones[i].push_back(j); ones[j].push_back(i); } } for(i=0;i<n;i++) { if(id[i]==0){ids++;dfs(i);} } for(i=0;i<n;i++) { if(!vis[i]) { groups[id[i]].push_back(i); ids++; solve(i); } } for(i=1;i<=ids;i++) { if(groups[i].size()==2)return 0; if(groups[i].size()<=2)continue; ans[groups[i][0]][groups[i][groups[i].size()-1]] = 1; for(j=1;j<groups[i].size();j++) { ans[groups[i][j-1]][groups[i][j]] = 1; } } ///std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { //std::vector<int> row; //row.resize(n); for(j=0;j<n;j++) { // row[j] = ans[i][j]|ans[j][i]; if(i==j)continue; if(p[i][j]==0&&id[i]==id[j]){return 0;} if(p[i][j]==1&&newids[i]!=newids[j])return 0; } //answer.push_back(row); } build(ans); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Incorrect | 1 ms | 364 KB | b is not symmetric: b[0][1] (1) != b[1][0] (0) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Incorrect | 1 ms | 364 KB | b is not symmetric: b[0][1] (1) != b[1][0] (0) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Incorrect | 1 ms | 364 KB | b is not symmetric: b[0][1] (1) != b[1][0] (0) |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Incorrect | 1 ms | 364 KB | b is not symmetric: b[0][1] (1) != b[1][0] (0) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Incorrect | 1 ms | 364 KB | b is not symmetric: b[0][1] (1) != b[1][0] (0) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Incorrect | 1 ms | 364 KB | b is not symmetric: b[0][1] (1) != b[1][0] (0) |
3 | Halted | 0 ms | 0 KB | - |