Submission #300393

#TimeUsernameProblemLanguageResultExecution timeMemory
300393DovranConnecting Supertrees (IOI20_supertrees)C++14
21 / 100
290 ms30308 KiB
#include <bits/stdc++.h> #include "supertrees.h" #define N 1009 #define ll long long #define pii pair<int, int> #define ff first #define ss second #define sz() size() #define pb push_back #define pp() pop_back() using namespace std; int n, sz[N], p[N]; vector<vector<int>>c; int vis[N][N]; vector<pii>a; vector<pii>b; /* void build(vector<vector<int>>m){ for(int i=0; i<m.sz(); i++){ for(int j=0; j<m[i].sz(); j++) cout<<m[i][j]<<' '; cout<<'\n'; } } */ int ata(int x){ if(p[x]==x) return x; return p[x]=ata(p[x]); } void dsu(int x, int y){ x=ata(x); y=ata(y); if(sz[y]>sz[x]) swap(x, y); sz[x]+=sz[y]; p[y]=x, sz[y]=0; return; } int construct(vector<vector<int>>v){ n=v.sz(); c.resize(n); for(int i=0; i<n; i++) sz[i]=1, p[i]=i; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ c[i].pb(0); if(v[i][j]==1 and i!=j) a.pb({i, j}), v[j][i]=3; if(v[i][j]==0) b.pb({i, j}); } } for(auto i:a){ if(ata(i.ff)!=ata(i.ss)) dsu(i.ff, i.ss), c[i.ff][i.ss]=c[i.ss][i.ff]=1; } int asd=0; for(auto i:b) if(ata(i.ff)==ata(i.ss)) asd=1; if(asd) return 0; build(c); return 1; } /* int main(){ int dsa, qwe; vector<vector<int>>v; cin>>dsa; v.resize(dsa); for(int i=0; i<dsa ;i++) for(int j=0; j<dsa; j++) cin>>qwe, v[i].pb(qwe); construct(v); } */
#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...