Submission #300660

#TimeUsernameProblemLanguageResultExecution timeMemory
300660OdaveyConnecting Supertrees (IOI20_supertrees)C++14
11 / 100
275 ms26824 KiB
// // ~oisín~ C++ Template // #include <bits/stdc++.h> #include "supertrees.h" #define MX_N 5001 #define mp make_pair #define mod7 1000000007 #define modpi 314159 #define PI 3.141592653589793238 #define pb push_back #define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define All(a) a.begin(),a.end() #define fi first #define se second #define ll long long int #define ull unsigned long long int int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1}; int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2}; int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1}; int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1}; int dx4[4] = {+0, +0, +1, -1}; int dy4[4] = {+1, -1, +0, +0}; ll gcd(ull a, ull b){ return (a==0)?b:gcd(b%a,a); } ll lcm(ull a, ull b){ return a*(b/gcd(a,b)); } const long long INF = 1e18; using namespace std; int n; //void build(vector<vector<int> > b){ // for(auto& v : b){ // for(int x : v){ // cout << x << ' '; // } // cout << endl; // } // cout << endl; // return; //} struct link{ link* par; int id; int m_id; }; link* find_set(link* at){ if(at == at->par){ return at; }else{ return at->par = find_set(at->par); } } void union_set(link* A, link* B){ link* a = find_set(A); link* b = find_set(B); if(a == b){ return; } a->par = b; return; } vector<int> adj[MX_N]; vector<int> familes[MX_N]; link* G[MX_N]; int construct(vector<vector<int> > p){ n = p.size(); auto res = p; for(auto& v : res){ for(int& x : v){ x = 0; } } for(int i=0;i<n;++i){ G[i] = new link; G[i]->id = i; G[i]->par = G[i]; } for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ if(p[i][j] == 1 || p[i][j] == 2){ adj[i].pb(j); adj[j].pb(i); union_set(G[i], G[j]); } } } for(int i=0;i<n;++i){ G[i]->m_id = familes[find_set(G[i])->id].size(); familes[find_set(G[i])->id].pb(i); } for(int i=0;i<n;++i){ G[i]->par = G[i]; } for(int f=0;f<n;++f){ if(familes[f].size() <= 1){ continue; } vector<int>& group = familes[f]; int m = group.size(); for(int i=0;i<m;++i){ for(int to : adj[group[i]]){ if(p[i][to] == 1){ union_set(G[i], G[to]); } } } vector<int> lots[m]; for(int i=0;i<m;++i){ lots[find_set(G[i])->m_id].pb(group[i]); } vector<int> circle; vector<vector<int> > chains; for(int i=0;i<m;++i){ if(lots[i].size() == 0){ continue; }else if(lots[i].size() == 1){ circle.pb(lots[i][0]); }else{ chains.pb(lots[i]); } } for(auto& chain : chains){ for(int i=1;i<(int)chain.size();++i){ res[chain[i]][chain[i-1]] = 1; res[chain[i-1]][chain[i]] = 1; } } for(int i=1;i<(int)chains.size();++i){ res[chains[i][0]][chains[i-1][0]] = 1; res[chains[i-1][0]][chains[i][0]] = 1; } for(int i=1;i<(int)circle.size();++i){ res[circle[i]][circle[i-1]] = 1; res[circle[i-1]][circle[i]] = 1; } if(circle.size() == 0){ continue; }else if(chains.size() == 0){ if(circle.size() == 2){ return 0; } res[circle[0]][circle[circle.size()-1]] = 1; res[circle[circle.size()-1]][circle[0]] = 1; }else{ res[circle[0]][chains[0][0]] = 1; res[chains[0][0]][circle[0]] = 1; res[circle[circle.size()-1]][chains[chains.size()-1][0]] = 1; res[chains[chains.size()-1][0]][circle[circle.size()-1]] = 1; } } build(res); 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...