# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1049941 | 2024-08-09T06:15:52 Z | mychecksedad | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 348 KB |
#include "supertrees.h" #include<bits/stdc++.h> using namespace std; #define ll long long int #define pb push_back #define vi vector<int> struct Dsu{ vector<int> p, s; Dsu(int n){ p.resize(n+1); s.resize(n+1,1); for(int i = 1; i <= n; ++i ) p[i]=i; } int find(int v){ if(p[v] == v)return v; return p[v]=find(p[v]); } void merge(int a, int b){ a = find(a); b = find(b); if(a != b){ if(s[a]>s[b]) swap(a,b); p[a] = b; s[b] += s[a]; } } }; vector<vector<int>> P; bool solve(vector<int> v, vector<vector<int>> &ans){ if(v.empty()) return 1; for(int u: v){ for(int x: v){ if(P[u][x] == 0 || P[u][x] == 3){ return 0; } } } vector<int> cycle; vector<vector<int>> onepiece; vector<bool> used(v.size()); for(int i = 0; i < v.size(); ++i){ bool fulltwo = 1; for(int j = i + 1; j < v.size(); ++j){ if(P[v[i]][v[j]] == 1){ fulltwo = 0; onepiece.pb(vector<int>{v[i], v[j]}); used[i] = used[j] = 1; for(int k = j + 1; k < v.size(); ++k){ if(!used[k]){ int co = 0; for(int c: onepiece.back()){ if(P[c][v[k]] == 1){ ++co; } } if(co != 0 && co != onepiece.back().size()){ return 0; } if(co == onepiece.back().size()){ onepiece.back().pb(v[k]); used[k] = 1; } } } } } if(fulltwo) cycle.pb(v[i]); // else assert(false); } for(auto x: onepiece){ for(int j = 0; j + 1 < x.size(); ++j){ ans[x[j]][x[j + 1]] = ans[x[j + 1]][x[j]] = 1; } cycle.pb(x[0]); } if(cycle.size() == 1 && v.size() == 1) return 1; if(cycle.size() == 1) return 0; for(int i = 0; i < cycle.size(); ++i){ ans[cycle[i]][cycle[(i + 1) % cycle.size()]] = ans[cycle[(i + 1) % cycle.size()]][cycle[i]] = 1; } return 1; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); P = p; vector<vector<int>> answer(n, vector<int>(n)); Dsu d(n); for(int i = 0; i < n; ++i){ for(int j = 1; j < n; ++j){ if(p[i][j] > 0) d.merge(i, j); } } vector<vector<int>> C(n); for(int i = 0; i < n; ++i){ C[d.find(i)].pb(i); } for(auto v: C){ bool ok = solve(v, answer); if(!ok) return 0; } build(answer); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | b[0][0] is not 0 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | b[0][0] is not 0 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Incorrect | 0 ms | 348 KB | Answer gives possible 1 while actual possible 0 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | b[1][1] is not 0 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | b[0][0] is not 0 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | b[0][0] is not 0 |
4 | Halted | 0 ms | 0 KB | - |