Submission #73726

#TimeUsernameProblemLanguageResultExecution timeMemory
73726TadijaSebezAirline Route Map (JOI18_airline)C++11
100 / 100
726 ms30744 KiB
#include "Alicelib.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair void Alice(int n, int m, int a[], int b[]) { int L=10; vector<pair<int,int> > edges; int cen=n+L,den=n+L+1,i,j; for(i=0;i<L-1;i++) edges.pb(mp(n+i,n+i+1)); vector<int> my(n,0);int k=0; for(i=0;i<n;i++) { while(__builtin_popcount(k)==9) k++; my[i]=k; edges.pb(mp(i,cen)); edges.pb(mp(i,den)); for(j=0;j<L;j++) if((my[i]>>j)&1) edges.pb(mp(i,n+j)); k++; } for(i=0;i<L;i++) edges.pb(mp(n+i,den)); for(i=0;i<m;i++) edges.pb(mp(a[i],b[i])); InitG(n+L+2,edges.size()); for(i=0;i<edges.size();i++) MakeG(i,edges[i].first,edges[i].second); }
#include "Boblib.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair vector<vector<int> > E; vector<int> fk,val; void DFS(int u, int p, int d) { val[u]=d; for(int v:E[u]) if(v!=p && fk[v]==1) DFS(v,u,d+1); } //set<pair<int,int> > es; bool has[1012][1012]; //bool has(int a, int b){ return has[a][b];} void AddEdge(int a, int b){ has[a][b]=has[b][a]=1;} void Bob(int n, int m, int a[], int b[]) { int L=10,N=n-L-2,i;E.clear();E.resize(n); vector<int> deg(n,0),my(1012,0); for(i=0;i<m;i++) deg[a[i]]++,deg[b[i]]++,AddEdge(a[i],b[i]); for(i=0;i<m;i++) E[a[i]].pb(b[i]),E[b[i]].pb(a[i]); int den,cen; for(i=0;i<n;i++) if(deg[i]==n-2) den=i; for(i=0;i<n;i++) { if(i==den) continue; if(has[i][den]) continue; cen=i; } int k=0,con=0; for(i=0;i<N;i++) { while(__builtin_popcount(k)==9) k++; my[k]=i;con+=k&1;k++; } fk.resize(n);fk[cen]=fk[den]=2;val.resize(n); for(i=0;i<n;i++) if(i!=cen && i!=den && !has[cen][i]) fk[i]=1; int one; for(i=0;i<n;i++) { if(fk[i]==1) { int c=0,d=0; for(int v:E[i]){ if(fk[v]==0) c++;if(fk[v]==1) d++;} if(c==con && d==1) one=i; } } DFS(one,-1,0); for(i=0;i<n;i++) if(fk[i]==0) { for(int v:E[i]) if(fk[v]==1) val[i]+=1<<val[v]; } vector<pair<int,int> > edges; for(i=0;i<m;i++) { if(fk[a[i]]==0 && fk[b[i]]==0) edges.pb(mp(my[val[a[i]]],my[val[b[i]]])); } InitMap(N,edges.size()); for(i=0;i<edges.size();i++) MakeMap(edges[i].first,edges[i].second); for(i=0;i<m;i++) has[a[i]][b[i]]=has[b[i]][a[i]]=0; /*int N=n-L-2,M=m-9-2*n,i,j; vector<int> indeg; indeg.resize(n); //for(i=0;i<N;i++) for(j=0;j<L;j++) if((i>>j)&1) M--; for(i=0;i<m;i++) indeg[a[i]]++; vector<int> real,fake,val,go,in; vector<bool> fk; for(i=0;i<n;i++){ if(indeg[i]>1) real.pb(i);else fake.pb(i);} fk.resize(n);go.resize(n);in.resize(n); for(i=0;i<fake.size();i++) fk[fake[i]]=1; //printf("Fake: ");for(i=0;i<fake.size();i++) printf("%i ",fake[i]);printf("\n"); for(i=0;i<n;i++) in[i]=go[i]=-1; for(i=0;i<m;i++) if(fk[a[i]] && fk[b[i]]) go[a[i]]=b[i],in[b[i]]=a[i]; int one; for(i=0;i<n;i++) if(go[i]!=-1 && in[i]==-1) one=i; val.resize(n); for(i=0;i<L;i++) val[one]=i,one=go[one]; for(i=0;i<m;i++) { if(!fk[a[i]] && fk[b[i]] && (go[b[i]]!=-1 || in[b[i]]!=-1)) val[a[i]]+=1<<val[b[i]]; } //printf("Val: ");for(i=0;i<n;i++) printf("%i ",val[i]);printf("\n"); vector<pair<int,int> > edges; for(i=0;i<m;i++) { if(!fk[a[i]] && !fk[b[i]]) { edges.pb(mp(val[a[i]],val[b[i]])); } } InitMap(N,edges.size()); for(i=0;i<edges.size();i++) MakeMap(edges[i].first,edges[i].second);*/ }

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:26:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<edges.size();i++) MakeG(i,edges[i].first,edges[i].second);
          ~^~~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:61:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<edges.size();i++) MakeMap(edges[i].first,edges[i].second);
          ~^~~~~~~~~~~~~
Bob.cpp:50:5: warning: 'one' may be used uninitialized in this function [-Wmaybe-uninitialized]
  DFS(one,-1,0);
  ~~~^~~~~~~~~~
Bob.cpp:39:33: warning: 'den' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for(i=0;i<n;i++) if(i!=cen && i!=den && !has[cen][i]) fk[i]=1;
                                ~^~~~~
Bob.cpp:39:23: warning: 'cen' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for(i=0;i<n;i++) if(i!=cen && i!=den && !has[cen][i]) fk[i]=1;
                      ~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...