# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
366890 | 2021-02-15T16:17:27 Z | rumen_m | Connecting Supertrees (IOI20_supertrees) | C++17 | 1000 ms | 35052 KB |
#include "supertrees.h" #include <vector> using namespace std; const int maxn = 1005; vector <int> g[maxn]; vector <int> ones[maxn]; int id[maxn], ids = 0; bool vis[maxn]; vector <int> groups[maxn]; int ans[maxn][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) { 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); 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]; 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 | 0 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 508 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 26 ms | 2924 KB | Output is correct |
7 | Execution timed out | 1055 ms | 22884 KB | Time limit exceeded |
# | 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 | 0 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 508 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 26 ms | 2924 KB | Output is correct |
7 | Execution timed out | 1055 ms | 22884 KB | Time limit exceeded |
# | 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 | 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 | 1388 KB | Output is correct |
9 | Correct | 259 ms | 24172 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 21 ms | 2540 KB | Output is correct |
13 | Execution timed out | 1089 ms | 18200 KB | Time limit exceeded |
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 | 364 KB | Output is correct |
4 | Correct | 71 ms | 8300 KB | Output is correct |
5 | Correct | 427 ms | 30188 KB | Output is correct |
6 | Correct | 262 ms | 26440 KB | Output is correct |
7 | Execution timed out | 1097 ms | 35052 KB | Time limit exceeded |
8 | 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 | 0 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 508 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 26 ms | 2924 KB | Output is correct |
7 | Execution timed out | 1055 ms | 22884 KB | Time limit exceeded |
# | 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 | 0 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 508 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 26 ms | 2924 KB | Output is correct |
7 | Execution timed out | 1055 ms | 22884 KB | Time limit exceeded |