# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
366896 | 2021-02-15T16:28:57 Z | rumen_m | Connecting Supertrees (IOI20_supertrees) | C++17 | 299 ms | 32296 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]; 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(); int i,j,t; 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(answer); return 1; }
Compilation message
# | 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 | 492 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 12 ms | 2156 KB | Output is correct |
7 | Correct | 299 ms | 32296 KB | Output is correct |
# | 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 | 492 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 12 ms | 2156 KB | Output is correct |
7 | Correct | 299 ms | 32296 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 11 ms | 1388 KB | Output is correct |
13 | Runtime error | 110 ms | 16620 KB | Execution killed with signal 11 |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 0 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 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 11 ms | 1260 KB | Output is correct |
9 | Runtime error | 112 ms | 16748 KB | Execution killed with signal 11 |
10 | 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 | 63 ms | 6892 KB | Output is correct |
5 | Correct | 253 ms | 25196 KB | Output is correct |
6 | Correct | 249 ms | 23728 KB | Output is correct |
7 | Correct | 291 ms | 28268 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 61 ms | 6892 KB | Output is correct |
10 | Runtime error | 118 ms | 21740 KB | Execution killed with signal 11 |
11 | 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 | 492 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 12 ms | 2156 KB | Output is correct |
7 | Correct | 299 ms | 32296 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 11 ms | 1388 KB | Output is correct |
13 | Runtime error | 110 ms | 16620 KB | Execution killed with signal 11 |
14 | 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 | 492 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 12 ms | 2156 KB | Output is correct |
7 | Correct | 299 ms | 32296 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 11 ms | 1388 KB | Output is correct |
13 | Runtime error | 110 ms | 16620 KB | Execution killed with signal 11 |
14 | Halted | 0 ms | 0 KB | - |