Submission #1080120

#TimeUsernameProblemLanguageResultExecution timeMemory
1080120GrindMachineConnecting Supertrees (IOI20_supertrees)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define pb push_back #define endl '\n' #define conts continue #define sz(a) (int)a.size() #define ff first #define ss second #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; ++i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &x, T y){ x = min(x,y); } template<typename T> void amax(T &x, T y){ x = max(x,y); } template<typename A,typename B> string to_string(pair<A,B> p); string to_string(const string &s){ return "'"+s+"'"; } string to_string(const char* s){ return to_string((string)s); } string to_string(bool b){ return b?"true":"false"; } template<typename A> string to_string(A v){ string res = "{"; trav(x,v){ res += to_string(x)+","; } if(res.back() == ',') res.pop_back(); res += "}"; return res; } template<typename A,typename B> string to_string(pair<A,B> p){ return "("+to_string(p.ff)+","+to_string(p.ss)+")"; } #define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl const int MOD = 1e9 + 7; const int N = 1e3 + 5; const int inf1 = 1e9 + 5; const ll inf2 = (ll)1e18 + 5; #include "supertrees.h" vector<int> par(N); void create(int n){ rep(i,n) par[i] = i; } int find(int u){ if(u == par[u]) return u; else return par[u] = find(par[u]); } void merge(int u, int v){ u = find(u), v = find(v); if(u == v) return; par[v] = u; } int construct(std::vector<std::vector<int>> a) { int n = a.size(); vector<vector<int>> ans(n,vector<int>(n)); create(n); rep(i,n){ rep(j,n){ if(a[i][j]){ merge(i,j); } } } rep(i,n){ rep(j,n){ int x = a[i][j] > 0; int y = find(i) == find(j); if(x != y){ return 0; } } } vector<int> group[n]; rep(i,n) group[find(i)].pb(i); auto f = [&](int u, int v){ ans[u][v] = ans[v][u] = 1; }; rep(c,n){ auto &nodes = group[c]; if(nodes.empty()) conts; create(n); vector<int> cc[n]; int m = sz(nodes); rep(i,m){ rep(j,i){ int u = nodes[i], v = nodes[j]; if(a[u][v] == 1){ merge(u,v); } } } rep(i,m){ rep(j,i){ int u = nodes[i], v = nodes[j]; int x = a[u][v] == 1; int y = find(u) == find(v); if(x != y){ return 0; } } } trav(u,nodes){ cc[find(u)].pb(u); } vector<int> cyc; rep(id,n){ if(cc[id].empty()) conts; auto &curr = cc[id]; cyc.pb(curr[0]); rep(i,sz(curr)-1){ f(curr[i],curr[i+1]); } } int siz = sz(cyc); if(siz <= 2) return 0; if(siz > 1){ rep(i,siz){ f(cyc[i],cyc[(i+1)%siz]); } } } build(ans); return 1; // std::vector<std::vector<int>> answer; // for (int i = 0; i < n; i++) { // std::vector<int> row; // row.resize(n); // answer.push_back(row); // } // build(answer); // 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...