제출 #1249000

#제출 시각아이디문제언어결과실행 시간메모리
1249000NurislamConnecting Supertrees (IOI20_supertrees)C++20
96 / 100
129 ms22196 KiB
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; struct dsu { vector<int> p, sz; dsu(int n) { p.resize(n); iota(p.begin(), p.end(), 0); sz.resize(n, 1); }; int f (int x) { return (p[x] == x? x: p[x] = f(p[x])); }; int unin(int x, int y) { x = f(x); y = f(y); if(x == y) return 0; if(sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; p[y] = x; return 1; }; }; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> ans(n, vector<int> (n)); dsu t(n); auto ad = [&](int x, int y) { ans[x][y] = 1; ans[y][x] = 1; t.unin(x, y); }; for(int i = 0; i < n; i ++ ) { for(int j = 0; j < n; j ++ ) { if(p[i][j] == 1 && t.unin(i, j)) ad(i, j); if(p[i][j] != p[j][i])return 0; }; }; vector<int> p2(n); {vector<int> ch(n); for(int i = 0; i < n; i ++ ) { if(ch[t.f(i)])continue; vector<int> vs(n), al; queue<int> q; for(int j = 0; j < n; j ++ ) { if(t.f(i) != t.f(j) && p[i][j] == 2) { q.push(t.f(i)); vs[t.f(i)] = 1; break; }; }; while(q.size()) { auto ps = q.front(); q.pop(); al.push_back(ps); ch[ps] = 1; for(int j = 0; j < n; j ++ ) { if(p[ps][j] == 3) return 0; if(vs[t.f(j)]) continue; if(ps != t.f(j) && p[ps][j] == 2) { q.push(t.f(j)); vs[t.f(j)] = 1; }; }; }; if(al.size() > 1 && al.size() <= 2) return 0; for(int j = 0; j < (int)al.size(); j ++ ) ad(al[j], al[(j+1) %al.size()]); if(al.size()) p2[t.f(i)] = 1; }; }; {vector<int> ch(n); for(int i = 0; i < n; i ++ ) { if(ch[t.f(i)])continue; vector<int> vs(n), al; queue<int> q; for(int j = 0; j < n; j ++ ) { if(t.f(i) != t.f(j) && p[i][j] == 3) { q.push(t.f(i)); vs[t.f(i)] = 1; break; }; }; while(q.size()) { auto ps = q.front(); if(p2[ps] == 1) return 0; q.pop(); al.push_back(ps); ch[ps] = 1; for(int j = 0; j < n; j ++ ) { if(vs[t.f(j)]) continue; if(ps != t.f(j) && p[ps][j] == 3) { q.push(t.f(j)); vs[t.f(j)] = 1; }; }; }; if(al.size() > 1 && al.size() <= 3) return 0; if(al.size() == 0)continue; for(int j = 0; j < (int)al.size(); j ++ ) ad(al[j], al[(j+1) %al.size()]); ad(al[0], al[2]); p2[t.f(i)] = 2; }; }; for(int i = 0; i < n; i ++ ) { for(int j = 0; j < n; j ++ ) { if(t.f(i) == t.f(j) && p[i][j] == 0) return 0; if(p[i][j] == 2 && (p2[t.f(i)] != 1 || p2[t.f(j)] != 1)) return 0; if(p[i][j] == 3 && (p2[t.f(i)] != 2 || p2[t.f(j)] != 2)) return 0; }; }; for(int i = 0; i < n; i ++ ) { if(p2[t.f(i)] == 1) for(int j = 0; j < n; j ++ ) if(p[i][j] == 3) return 0; }; build(ans); return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...