Submission #619703

#TimeUsernameProblemLanguageResultExecution timeMemory
619703AriaHConnecting Supertrees (IOI20_supertrees)C++17
0 / 100
1 ms340 KiB
#include "supertrees.h" /* I can do this all day */ #pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair < int, int > pii; typedef pair < ll, ll > pll; #define F first #define S second #define all(x) x.begin(),x.end() #define Mp make_pair #define point complex #define endl '\n' #define SZ(x) (int)x.size() #define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout); const int N = 1e3 + 10; const int LOG = 20; const ll mod = 1e9 + 7; const ll inf = 8e18; const double pi = acos(-1); const ld eps = 1e-18; const ld one = 1.; ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int par[N]; vector < int > mol[N], vec[N]; vector < vector < int > > Ans; inline void add(int i, int j) { Ans[i][j] = Ans[j][i] = 1; } int get(int x) { return (x == par[x]? x : par[x] = get(par[x])); } void unify(int v, int u) { v = get(v), u = get(u); if(v == u) return; par[u] = v; } int construct(vector < vector < int > > A) { int n = SZ(A); for(int i = 0; i < n; i ++) par[i] = i; Ans.resize(n); for(int i = 0; i < n; i ++) { Ans[i].resize(n, 0); if(A[i][i] != 1) return 0; for(int j = 0; j < n; j ++) { if(i == j) continue; if(A[i][j] == 3) return 0; if(A[i][j]) { unify(i, j); } } } for(int i = 0; i < n; i ++) { mol[get(i)].push_back(i); } for(int i = 0; i < n; i ++) { /// the connected component check for(auto x : mol[i]) { for(auto y : mol[i]) { if(A[x][y] == 0) return 0; } } } for(int i = 0; i < n; i ++) par[i] = i; for(int i = 0; i < n; i ++) { for(auto x : mol[i]) { for(auto y : mol[i]) { if(A[x][y] == 1) { unify(x, y); } } } } for(int i = 0; i < n; i ++) { vec[get(i)].push_back(i); } for(int i = 0; i < n; i ++) { for(auto x : vec[i]) { for(auto y : vec[i]) { if(A[x][y] != 1) { return 0; } } } for(int j = 1; j < SZ(vec[i]); j ++) { add(vec[i][j - 1], vec[i][j]); } } for(int i = 0; i < n; i ++) { vector < int > cyc; for(auto x : mol[i]) { /*if(x == get(x)) { cyc.push_back(x); }*/ cyc.push_back(x); } int sz = SZ(cyc); if(sz <= 1) continue; for(int j = 0; j < sz; j ++) { add(cyc[j], cyc[(j + 1) % sz]); } } 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...