Submission #1041100

#TimeUsernameProblemLanguageResultExecution timeMemory
1041100edogawa_somethingAirline Route Map (JOI18_airline)C++17
37 / 100
215 ms19912 KiB
#include "Alicelib.h" #include <bits/stdc++.h> using namespace std; #define pb push_back bool mp[50][50]; vector<int> v[1500]; void Alice( int N, int M, int A[], int B[] ){ if(N==1) { InitG(1,0); return; } if(N==2) { if(M==1) InitG(3,0); else InitG(2,0); return; } for(int i=0;i<M;i++) mp[A[i]][B[i]]=1,mp[B[i]][A[i]]=1; v[0].pb(2); v[1].pb(2); v[2].pb(3); for(int i=3;i<=3+(N*(N-1))/2;i++) v[i].pb(i+1); int cnt=0; for(int i=0;i<N;i++) { for(int j=i+1;j<N;j++) { if(mp[i][j]) v[cnt+4].pb(2); cnt++; } } int ecnt=0; for(int i=0;i<1500;i++) ecnt+=v[i].size(); cnt=0; InitG(5+(N*(N-1))/2,ecnt); for(int i=0;i<1500;i++) { for(auto it:v[i]) { MakeG(cnt++,i,it); } } }
#include "Boblib.h" #include <bits/stdc++.h> using namespace std; #define pb push_back vector<int>adj[1500]; bool cnt[1500]; bool vis[1500]; vector<int>v1,vv; void dfs(int x,int target) { if(vis[x]) return; vis[x]=1; vv.pb(x); for(auto it:adj[x]) { if(vv.size()==2) { if(adj[it].size()==2) dfs(it,target); else continue; } if(!vis[it]) dfs(it,target); } if(vv.size()>v1.size()) v1=vv; vv.pop_back(); } void Bob( int V, int U, int C[], int D[] ){ if(U==0) { if(V==1) { InitMap(1,0); } else if(V==2) { InitMap(2,0); } else { InitMap(2,1); MakeMap(0,1); } return; } for(int i=0;i<U;i++) { adj[C[i]].pb(D[i]),adj[D[i]].pb(C[i]); } for(int i=0;i<V;i++) { if(adj[i].size()==1) { v1.pb(i); } } if(v1.size()==2) { int x=v1[0]; v1.clear(); dfs(x,V-1); } else if(v1.size()==3) { bool c=0; for(auto it:adj[v1[0]]) { for(auto itt:adj[it]) { if(itt==v1[1]||itt==v1[2]) c=1; } } int x; if(c) x=v1[0], v1.clear(), dfs(x,V-1); else x=v1[1],v1.clear(), dfs(x,V-1); } for(int i=3;i<v1.size();i++) { for(auto it:adj[v1[i]]) { if(it==v1[1]) { cnt[i-3]=1; } } } int c=0; int n=V-4; int l=3,r=40,mid; while(l<=r) { mid=((l+r)>>1); if(mid*(mid-1)/2>=V-5) n=mid,r=mid-1; else l=mid+1; } vector<pair<int,int>>edge; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(cnt[c]) edge.pb({i,j}); c++; } } InitMap(n,edge.size()); for(auto it:edge) MakeMap(it.first,it.second); }

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=3;i<v1.size();i++) {
      |               ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...