# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
827006 | 2023-08-16T07:56:02 Z | tomruk | Connecting Supertrees (IOI20_supertrees) | C++17 | 172 ms | 22064 KB |
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> answer(n,(vector<int>(n,0))); vector<bool> used(n,0); function<void(int)> dfs = [&](int v)->void{ used[v] = 1; for(int i = 0;i<n;i++){ // cout << v << ' ' << i << endl; // cout << p[v][i] << endl; if(!used[i] && p[v][i]){ dfs(i); answer[v][i] = 1; answer[i][v] = 1; } } }; for(int i = 0;i<n;i++){ if(used[i])continue; int now = i; vector<int> tmp; int num = -1; set<int> s; for(int j = 0;j<n;j++){ if(p[now][j] >= 2){ if(num == -1) num = p[now][j]; if(num != p[now][j]) return 0; s.insert(j); } } while(s.size()){ tmp.push_back(now); used[now] = 1; vector<int> del; for(auto u:s){ if(p[now][u] < 2){ del.push_back(u); } } for(auto u:del) s.erase(u); if(s.empty()) break; now = *s.begin(); } if(tmp.empty()) continue; if(tmp.size() < 3){ return 0; } for(int i = 0;i<tmp.size();i++){ answer[tmp[i]][tmp[(i + 1)%tmp.size()]] = 1; answer[tmp[(i + 1)%tmp.size()]][tmp[i]] = 1; } if(num == 3){ if(tmp.size() < 4) return 0; answer[tmp[i]][tmp[(i + 2)%tmp.size()]] = 1; answer[tmp[(i + 2)%tmp.size()]][tmp[i]] = 1; } for(auto u:tmp){ dfs(u); } } for(int i = 0;i<n;i++){ // cout << used[i] << endl; if(!used[i]) dfs(i); } build(answer); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 6 ms | 1108 KB | Output is correct |
7 | Correct | 151 ms | 22064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 6 ms | 1108 KB | Output is correct |
7 | Correct | 151 ms | 22064 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 6 ms | 1144 KB | Output is correct |
13 | Correct | 148 ms | 22028 KB | Output is correct |
14 | Incorrect | 0 ms | 212 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 | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 7 ms | 1108 KB | Output is correct |
9 | Correct | 151 ms | 21988 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 6 ms | 1108 KB | Output is correct |
13 | Correct | 155 ms | 22016 KB | Output is correct |
14 | Incorrect | 0 ms | 212 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 | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 38 ms | 5752 KB | Output is correct |
5 | Correct | 152 ms | 22016 KB | Output is correct |
6 | Correct | 149 ms | 21976 KB | Output is correct |
7 | Correct | 154 ms | 21992 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 38 ms | 5716 KB | Output is correct |
10 | Correct | 172 ms | 22020 KB | Output is correct |
11 | Correct | 151 ms | 22028 KB | Output is correct |
12 | Correct | 154 ms | 21964 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Incorrect | 38 ms | 5660 KB | Too many ways to get from 23 to 253, should be 1 found no less than 2 |
17 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 6 ms | 1108 KB | Output is correct |
7 | Correct | 151 ms | 22064 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 6 ms | 1144 KB | Output is correct |
13 | Correct | 148 ms | 22028 KB | Output is correct |
14 | Incorrect | 0 ms | 212 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 | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 6 ms | 1108 KB | Output is correct |
7 | Correct | 151 ms | 22064 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 6 ms | 1144 KB | Output is correct |
13 | Correct | 148 ms | 22028 KB | Output is correct |
14 | Incorrect | 0 ms | 212 KB | Answer gives possible 1 while actual possible 0 |
15 | Halted | 0 ms | 0 KB | - |