제출 #431351

#제출 시각아이디문제언어결과실행 시간메모리
431351Pbezz슈퍼트리 잇기 (IOI20_supertrees)C++14
46 / 100
314 ms22140 KiB
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back typedef pair<ll,ll> pii; const ll MAXN = 2e5+5; int parent[MAXN],sizee[MAXN],contagem[MAXN]; int parent1[MAXN],sizee1[MAXN]; int find(ll x){ if(x==parent[x])return x; return parent[x]=find(parent[x]); } void unite(ll a, ll b){ a = find(a); b = find(b); if(a==b)return; if(sizee[a]<sizee[b])swap(a,b); sizee[a]+=sizee[b]; parent[b]=a; } int find1(ll x){ if(x==parent1[x])return x; return parent1[x]=find1(parent1[x]); } void unite1(ll a, ll b){ a = find1(a); b = find1(b); if(a==b)return; if(sizee1[a]<sizee1[b])swap(a,b); sizee1[a]+=sizee1[b]; parent1[b]=a; } int construct(std::vector<std::vector<int>> p) { int n = p.size(),i,j,k,a,b; std::vector<std::vector<int>> answer; for (i = 0; i < n; i++) { std::vector<int> row; row.resize(n); answer.push_back(row); } for(i=0;i<n;i++){ parent[i]=i; sizee[i]=1; parent1[i]=i; sizee1[i]=1; } for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ if(p[i][j]==0)continue; contagem[i]++; contagem[j]++; unite(i,j); } } vector<vector<int>>meh(n); for(i=0;i<n;i++){ k=find(i); meh[k].pb(i); }//meh[i] e set da componente de i for(a=0;a<n;a++){ if(a!=find(a))continue;//para cada componente k = meh[a].size();//cout<<a<<" "<<k<<endl; for(i=0;i<k;i++){ for(j=i+1;j<k;j++){ if(p[ meh[a][i] ][ meh[a][j] ]!=1)continue; unite1(meh[a][i],meh[a][j]); } }//componentes feitas vector<vector<int>>meh1(n); for(i=0;i<k;i++){ b=find1(meh[a][i]); meh1[b].pb(meh[a][i]); } vector<int>fina; for(i=0;i<k;i++){ if(find1(meh[a][i])!=meh[a][i])continue; for(j=1;j<(int)meh1[ meh[a][i] ].size();j++){//fazer linha answer[ meh1[ meh[a][i] ][j] ][ meh1[ meh[a][i] ][j-1] ]=1; answer[ meh1[ meh[a][i] ][j-1] ][ meh1[ meh[a][i] ][j] ]=1; } fina.pb(meh[a][i]); } for(j=1;j<(int)fina.size();j++){ answer[ fina[j] ][ fina[j-1] ]=1; answer[ fina[j-1] ][ fina[j] ]=1; } if(fina.size()>1){ answer[ fina[(int)fina.size()-1] ][ fina[0] ]=1; answer[ fina[0] ][ fina[(int)fina.size()-1] ]=1; } } 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...