Submission #47043

#TimeUsernameProblemLanguageResultExecution timeMemory
47043vanogamAirline Route Map (JOI18_airline)C++14
100 / 100
830 ms25468 KiB
#include "Alicelib.h" #include <bits/stdc++.h> using namespace std; void Alice( int N, int M, int A[], int B[] ){ int a=0,u=0; a+=N+10+10+M+12; for(int i=0;i<N;i++){ a+=__builtin_popcount(i); } InitG( N+12, a ); for(int i=0;i<N;i++){ MakeG(u++,i,N+10); //MakeG(u++,i,N+11);//cout<<"*"; } for(int i=N;i<N+10;i++){ MakeG(u++,i,N+10); MakeG(u++,i,N+11); if(i!=N+9) MakeG(u++,i,i+1); //else MakeG(u++,N,i+2); } MakeG(u++,N,N+5); MakeG(u++,N,N+6); MakeG(u++,N,N+7); for(int i=0;i<M;i++) MakeG(u++,A[i],B[i]); for(int i=0;i<N;i++){ for(int a=0;a<10;a++){ if(i&(1<<a)) MakeG(u++,i,N+a); } } }
#include "Boblib.h" #include <bits/stdc++.h> using namespace std; void Bob( int V, int U, int C[], int D[] ){ vector<int> v[1102]; int d[1102][1102],f[1102],g[1102]; int k=0; for(int i=0;i<U;i++){ //cout<<C[i]<<" "<<D[i]<<endl; v[C[i]].push_back(D[i]); v[D[i]].push_back(C[i]); d[C[i]][D[i]]=1; d[D[i]][C[i]]=1; } for(int i=0;i<V;i++){ sort(v[i].begin(),v[i].end()); //for(auto it:v[i]) cout<<i<<" "<<it<<endl; } for(int i=0;i<V;i++){ if(v[i].size()==V-2) {k=i;break;} } f[k]=-10; g[k]=2; for(auto it:v[k]) g[it]=1; for(int i=0;i<V;i++){ if(!g[i]) {k=i;break;} }g[k]=2; f[k]=-10; for(int i=0;i<V;i++){ if(!d[k][i]) g[i]=2; } for(int i=0;i<V;i++){ if(g[i]==2) continue;//cout<<"**"<<i<<"**"; for(int a=i+1;a<V;a++){ if(g[a]==2) continue; if(d[i][a]){f[i]--;f[a]--;} } } for(int i=0;i<V;i++){//cout<<f[i]<<"&"; if(f[i]==-4) {k=i;break;} } int xr=1,l=0; for(int i=0;i<10;i++){ for(auto it:v[k]){ if(f[it]>=0) {f[it]+=xr;} if(f[it]==-10) continue;//cout<<f[it]<<" "; if(f[it]==-3 && f[k]!=-4) {l=it;} if(f[it]==-2 || f[it]==-1) {l=it;} }//cout<<endl; f[k]=-10;//cout<<f[0]<<"**"<<endl; k=l; xr*=2; } for(int i=0;i<V;i++){ if(f[i]>=0){ for(auto it:v[i]){ if(f[it]>=0) {d[i][it]=2;d[it][i]=2;} } } } int m=0; for(int i=0;i<V;i++){ if(f[i]<0) continue; for(int a=i+1;a<V;a++){ if(f[a]<0) continue; if(d[i][a]==2) m++; } }//cout<<"**"<<m<<"**"; InitMap(V-12,m); for(int i=0;i<V;i++){ if(f[i]<0) continue; for(int a=i+1;a<V;a++){ if(f[a]<0) continue; if(d[i][a]==2){MakeMap(f[i],f[a]);} } } }

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v[i].size()==V-2) {k=i;break;}
            ~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...