Submission #616054

#TimeUsernameProblemLanguageResultExecution timeMemory
616054PanTkdConnecting Supertrees (IOI20_supertrees)C++14
0 / 100
1 ms228 KiB
// // main.cpp // // Created by Panagiotis Chadjicostas on // Copyright © Panagiotis Hadjicostas. All rights reserved. // #include "supertrees.h" #include <iostream> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <fstream> #include <iomanip> #include <iterator> #include <limits> #include <list> #include <cstring> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #include <unordered_map> using namespace std; typedef int ll; typedef vector<ll> vi; typedef pair<ll,ll> ii; #define fo(i,a,b) for(int i = a; i<=b; i++) #define f(i,b) for(int i=0;i<b;i++) #define F first #define S second #define sz size #define ls s,m,idx<<1 #define rs m+1,e,idx<<1|1 const ll MOD=ll(1e9)+7; const ll MAXN=2*ll(1e6); void checker(){ ll n=rand()%20+2; vi a(n,ll()); for(ll i=0;i<n;i++){ a[i]=rand()%20+2; } for(ll b=0;b<(1<<n);b++){ vi on,off; for(ll i=0;i<n;i++){ if(i&(1<<i)){ on.push_back(i); } else{ off.push_back(i); } } } } /////////////////////////////////////////////////////////////////////// void build(vector<vector<ll> > b); vi parent ; int find(int x){ if(parent[x]==x) return x; parent[x]=find(parent[x]); return parent[x]; } void onion(int x, int y){ parent[find(y)]=find(x); return; } vector<vi> A,B; vi V; void dfs(ll s){ V[s]=1; for(auto x:A[s]) if(!V[x]) dfs(x); } int construct(vector<vector<ll> > p) { ll s=0; ll n=p.size(); vector<vector<ll> > ans (n, vector<int>(n, 0)); parent.assign(n,0); for(ll i=0;i<n;i++) parent[i]=i; for(ll i=0;i<n;i++) for(ll j=0;j<n;j++){ if(p[i][j]==1){ onion(i,j); } } /* for(ll i=0;i<n;i++) for(ll j=0;j<n;j++) if(i!=j) if(!p[i][j]&&parent[i]==parent[j]) return 0; */ V.assign(n,0); A.assign(n,vi()); B.assign(n,vi()); /* ll counter=0; for(ll i=0;i<n;i++){ if(!V[i]){ dfs(i); counter++; } } cout<<"Vrika tosa diaforetika: "<<counter<<endl; */ for(ll i=0;i<n;i++){ find(i); //cout<<i<<' '<<parent[i]<<endl; }for(ll i=0;i<n;i++) B[parent[i]].push_back(i); for(ll i=0;i<n;i++){ ll cur=-1; if(B[i].empty())continue; for(auto x:B[i]){ for(auto y:B[i]){ if(x!=y){ if(cur!=-1) cur=p[x][y]; else if(p[x][y]!=cur) return 0; } } } } for(ll i=0;i<n;i++){ if(!B[i].empty()){ if(p[i][B[i][1]]!=2)continue; for(ll j=0;j<B[i].size()-1;j++){ ans[B[i][j]][B[i][j+1]]=1; ans[B[i][j+1]][B[i][j]]=1; } ans[B[i][0]][B[i][B[i].size()-1]]=1; ans[B[i][B[i].size()-1]][B[i][0]]=1; } } build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:144:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |             for(ll j=0;j<B[i].size()-1;j++){
      |                        ~^~~~~~~~~~~~~~
supertrees.cpp:84:8: warning: unused variable 's' [-Wunused-variable]
   84 |     ll s=0;
      |        ^
#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...