# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
486528 | 2021-11-11T21:59:37 Z | A_D | Connecting Supertrees (IOI20_supertrees) | C++14 | 187 ms | 30888 KB |
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int N=1e3+100; vector<int> g[N]; vector<int> g2[N]; bool vis[N]; bool ccc[N]; vector<vector<int>> answer; int pp[N]; int c[N]; vector<int> vec; vector<int> vec2; int ret=1,n; int find(int u) { if(u==pp[u])return u; return pp[u]=find(pp[u]); } void dfs(int u) { vec2.push_back(u); if(vis[u])return; vis[u]=1; for(auto x:g[u]){ if(vis[x])continue; answer[u][x]=1; answer[x][u]=1; pp[find(u)]=pp[find(x)]; dfs(x); } } int construct(vector<vector<int>> p) { n = p.size(); for (int i = 0; i < n; i++) { pp[i]=i; vector<int> row(n); answer.push_back(row); } for(int i=0;i<n;i++){ if(p[i][i]!=1)return 0; for(int j=0;j<n;j++){ if(p[i][j]==1){ g[i].push_back(j); g[j].push_back(i); } } } for(int u=0;u<n;u++){ dfs(u); for(int i=1;i<vec2.size();i++){ for(int j=0;j<n;j++){ if(vec2[i]==j||vec2[i-1]==j)continue; if(p[vec2[i]][j]!=p[vec2[i-1]][j])return 0; } } vec2.clear(); } for(int i=0;i<n;i++){ if(pp[i]==i)vec.push_back(i); } int sz=vec.size(); for(int i1=0;i1<sz;i1++){ for(int j1=i1+1;j1<sz;j1++){ int i=vec[i1]; int j=vec[j1]; ccc[i]=1; if(p[i][j]==3)return -1; if(p[i][j]==2){ answer[i][j]=1; answer[j][i]=1; break; } } } for(int i1=0;i1<sz;i1++){ for(int j1=sz-1;j1>i1;j1--){ int i=vec[i1]; int j=vec[j1]; if(p[i][j]==2&&ccc[j]==0){ ccc[j]=1; answer[i][j]++; answer[j][i]++; if(answer[i][j]==2){ // cout<<i<<" "<<j<<endl; return 0; } break; } } } build(answer); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 8 ms | 1740 KB | Output is correct |
7 | Correct | 186 ms | 30888 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 8 ms | 1740 KB | Output is correct |
7 | Correct | 186 ms | 30888 KB | Output is correct |
8 | Correct | 0 ms | 332 KB | Output is correct |
9 | Correct | 0 ms | 332 KB | Output is correct |
10 | Correct | 0 ms | 332 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 7 ms | 1228 KB | Output is correct |
13 | Correct | 171 ms | 22716 KB | Output is correct |
14 | Correct | 0 ms | 332 KB | Output is correct |
15 | Correct | 1 ms | 432 KB | Output is correct |
16 | Correct | 4 ms | 1104 KB | Output is correct |
17 | Correct | 88 ms | 19892 KB | Output is correct |
18 | Correct | 0 ms | 336 KB | Output is correct |
19 | Correct | 0 ms | 336 KB | Output is correct |
20 | Correct | 43 ms | 6340 KB | Output is correct |
21 | Correct | 171 ms | 25128 KB | Output is correct |
22 | Correct | 166 ms | 24136 KB | Output is correct |
23 | Correct | 181 ms | 28232 KB | Output is correct |
24 | Correct | 163 ms | 24096 KB | Output is correct |
25 | Correct | 76 ms | 15180 KB | Output is correct |
26 | Correct | 71 ms | 14156 KB | Output is correct |
27 | Correct | 180 ms | 30184 KB | Output is correct |
28 | Correct | 165 ms | 24116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 332 KB | Output is correct |
7 | Correct | 0 ms | 332 KB | Output is correct |
8 | Correct | 7 ms | 1256 KB | Output is correct |
9 | Correct | 176 ms | 22708 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 7 ms | 1264 KB | Output is correct |
13 | Correct | 166 ms | 22660 KB | Output is correct |
14 | Incorrect | 1 ms | 332 KB | Answer gives possible 1 while actual possible 0 |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 42 ms | 6360 KB | Output is correct |
5 | Correct | 170 ms | 23760 KB | Output is correct |
6 | Correct | 168 ms | 22788 KB | Output is correct |
7 | Correct | 187 ms | 27016 KB | Output is correct |
8 | Incorrect | 0 ms | 332 KB | Too few ways to get from 0 to 1, should be 2 found 1 |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 8 ms | 1740 KB | Output is correct |
7 | Correct | 186 ms | 30888 KB | Output is correct |
8 | Correct | 0 ms | 332 KB | Output is correct |
9 | Correct | 0 ms | 332 KB | Output is correct |
10 | Correct | 0 ms | 332 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 7 ms | 1228 KB | Output is correct |
13 | Correct | 171 ms | 22716 KB | Output is correct |
14 | Correct | 0 ms | 332 KB | Output is correct |
15 | Correct | 1 ms | 432 KB | Output is correct |
16 | Correct | 4 ms | 1104 KB | Output is correct |
17 | Correct | 88 ms | 19892 KB | Output is correct |
18 | Correct | 0 ms | 336 KB | Output is correct |
19 | Correct | 0 ms | 336 KB | Output is correct |
20 | Correct | 43 ms | 6340 KB | Output is correct |
21 | Correct | 171 ms | 25128 KB | Output is correct |
22 | Correct | 166 ms | 24136 KB | Output is correct |
23 | Correct | 181 ms | 28232 KB | Output is correct |
24 | Correct | 163 ms | 24096 KB | Output is correct |
25 | Correct | 76 ms | 15180 KB | Output is correct |
26 | Correct | 71 ms | 14156 KB | Output is correct |
27 | Correct | 180 ms | 30184 KB | Output is correct |
28 | Correct | 165 ms | 24116 KB | Output is correct |
29 | Correct | 1 ms | 332 KB | Output is correct |
30 | Correct | 0 ms | 332 KB | Output is correct |
31 | Correct | 1 ms | 332 KB | Output is correct |
32 | Correct | 0 ms | 332 KB | Output is correct |
33 | Correct | 0 ms | 348 KB | Output is correct |
34 | Correct | 0 ms | 332 KB | Output is correct |
35 | Correct | 0 ms | 332 KB | Output is correct |
36 | Correct | 7 ms | 1256 KB | Output is correct |
37 | Correct | 176 ms | 22708 KB | Output is correct |
38 | Correct | 1 ms | 332 KB | Output is correct |
39 | Correct | 0 ms | 332 KB | Output is correct |
40 | Correct | 7 ms | 1264 KB | Output is correct |
41 | Correct | 166 ms | 22660 KB | Output is correct |
42 | Incorrect | 1 ms | 332 KB | Answer gives possible 1 while actual possible 0 |
43 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 8 ms | 1740 KB | Output is correct |
7 | Correct | 186 ms | 30888 KB | Output is correct |
8 | Correct | 0 ms | 332 KB | Output is correct |
9 | Correct | 0 ms | 332 KB | Output is correct |
10 | Correct | 0 ms | 332 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 7 ms | 1228 KB | Output is correct |
13 | Correct | 171 ms | 22716 KB | Output is correct |
14 | Correct | 0 ms | 332 KB | Output is correct |
15 | Correct | 1 ms | 432 KB | Output is correct |
16 | Correct | 4 ms | 1104 KB | Output is correct |
17 | Correct | 88 ms | 19892 KB | Output is correct |
18 | Correct | 0 ms | 336 KB | Output is correct |
19 | Correct | 0 ms | 336 KB | Output is correct |
20 | Correct | 43 ms | 6340 KB | Output is correct |
21 | Correct | 171 ms | 25128 KB | Output is correct |
22 | Correct | 166 ms | 24136 KB | Output is correct |
23 | Correct | 181 ms | 28232 KB | Output is correct |
24 | Correct | 163 ms | 24096 KB | Output is correct |
25 | Correct | 76 ms | 15180 KB | Output is correct |
26 | Correct | 71 ms | 14156 KB | Output is correct |
27 | Correct | 180 ms | 30184 KB | Output is correct |
28 | Correct | 165 ms | 24116 KB | Output is correct |
29 | Correct | 1 ms | 332 KB | Output is correct |
30 | Correct | 0 ms | 332 KB | Output is correct |
31 | Correct | 1 ms | 332 KB | Output is correct |
32 | Correct | 0 ms | 332 KB | Output is correct |
33 | Correct | 0 ms | 348 KB | Output is correct |
34 | Correct | 0 ms | 332 KB | Output is correct |
35 | Correct | 0 ms | 332 KB | Output is correct |
36 | Correct | 7 ms | 1256 KB | Output is correct |
37 | Correct | 176 ms | 22708 KB | Output is correct |
38 | Correct | 1 ms | 332 KB | Output is correct |
39 | Correct | 0 ms | 332 KB | Output is correct |
40 | Correct | 7 ms | 1264 KB | Output is correct |
41 | Correct | 166 ms | 22660 KB | Output is correct |
42 | Incorrect | 1 ms | 332 KB | Answer gives possible 1 while actual possible 0 |
43 | Halted | 0 ms | 0 KB | - |