# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
367117 | 2021-02-16T10:16:35 Z | MilosMilutinovic | Connecting Supertrees (IOI20_supertrees) | C++14 | 275 ms | 31212 KB |
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; #define pb push_back const int N=1050; vector<int> E[N]; vector<vector<int>> p; void AddEdge(int u,int v){E[u].pb(v);E[v].pb(u);} vector<int> Euler; bool was[N]; void DFS1(int u){ was[u]=true,Euler.pb(u); for(int v:E[u])if(!was[v]&&p[u][v]==1)DFS1(v); } int construct(vector<vector<int>> P){ p=P;int n=(int)P.size(); for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(p[i][j]>0)AddEdge(i,j); bool one=false,two=false; for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(p[i][j]==1)one=true; for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(p[i][j]==2)two=true; vector<vector<int>> ans(n,vector<int>(n,0)); if(!one&&!two){build(ans);return 1;} if(one&&!two){ for(int i=0;i<n;i++){ if(!was[i]){ DFS1(i); if((int)Euler.size()==1){Euler.clear();continue;} for(int x:Euler)for(int y:Euler)if(x!=y&&p[x][y]==0)return 0; for(int i=1;i<(int)Euler.size();i++){ int x=Euler[i],y=Euler[i-1]; ans[x][y]=ans[y][x]=1; } Euler.clear(); } } build(ans); 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 | 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 | 11 ms | 1644 KB | Output is correct |
7 | Correct | 275 ms | 30188 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 | 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 | 11 ms | 1644 KB | Output is correct |
7 | Correct | 275 ms | 30188 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 | 10 ms | 1516 KB | Output is correct |
13 | Correct | 246 ms | 28140 KB | Output is correct |
14 | Correct | 1 ms | 492 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 5 ms | 1260 KB | Output is correct |
17 | Correct | 121 ms | 20972 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 65 ms | 7404 KB | Output is correct |
21 | Correct | 249 ms | 28524 KB | Output is correct |
22 | Correct | 244 ms | 28028 KB | Output is correct |
23 | Correct | 255 ms | 30060 KB | Output is correct |
24 | Correct | 246 ms | 28140 KB | Output is correct |
25 | Correct | 109 ms | 18668 KB | Output is correct |
26 | Correct | 106 ms | 18156 KB | Output is correct |
27 | Correct | 261 ms | 31212 KB | Output is correct |
28 | Correct | 249 ms | 28012 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 | 364 KB | Output is correct |
4 | Runtime error | 3 ms | 620 KB | Execution killed with signal 6 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Runtime error | 3 ms | 620 KB | Execution killed with signal 6 |
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 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 11 ms | 1644 KB | Output is correct |
7 | Correct | 275 ms | 30188 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 | 10 ms | 1516 KB | Output is correct |
13 | Correct | 246 ms | 28140 KB | Output is correct |
14 | Correct | 1 ms | 492 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 5 ms | 1260 KB | Output is correct |
17 | Correct | 121 ms | 20972 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 65 ms | 7404 KB | Output is correct |
21 | Correct | 249 ms | 28524 KB | Output is correct |
22 | Correct | 244 ms | 28028 KB | Output is correct |
23 | Correct | 255 ms | 30060 KB | Output is correct |
24 | Correct | 246 ms | 28140 KB | Output is correct |
25 | Correct | 109 ms | 18668 KB | Output is correct |
26 | Correct | 106 ms | 18156 KB | Output is correct |
27 | Correct | 261 ms | 31212 KB | Output is correct |
28 | Correct | 249 ms | 28012 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 1 ms | 364 KB | Output is correct |
31 | Correct | 1 ms | 364 KB | Output is correct |
32 | Runtime error | 3 ms | 620 KB | Execution killed with signal 6 |
33 | 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 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 11 ms | 1644 KB | Output is correct |
7 | Correct | 275 ms | 30188 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 | 10 ms | 1516 KB | Output is correct |
13 | Correct | 246 ms | 28140 KB | Output is correct |
14 | Correct | 1 ms | 492 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 5 ms | 1260 KB | Output is correct |
17 | Correct | 121 ms | 20972 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 65 ms | 7404 KB | Output is correct |
21 | Correct | 249 ms | 28524 KB | Output is correct |
22 | Correct | 244 ms | 28028 KB | Output is correct |
23 | Correct | 255 ms | 30060 KB | Output is correct |
24 | Correct | 246 ms | 28140 KB | Output is correct |
25 | Correct | 109 ms | 18668 KB | Output is correct |
26 | Correct | 106 ms | 18156 KB | Output is correct |
27 | Correct | 261 ms | 31212 KB | Output is correct |
28 | Correct | 249 ms | 28012 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 1 ms | 364 KB | Output is correct |
31 | Correct | 1 ms | 364 KB | Output is correct |
32 | Runtime error | 3 ms | 620 KB | Execution killed with signal 6 |
33 | Halted | 0 ms | 0 KB | - |