Submission #1280944

#TimeUsernameProblemLanguageResultExecution timeMemory
1280944AvianshAirline Route Map (JOI18_airline)C++20
37 / 100
2591 ms61032 KiB
#include "Alicelib.h" #include <cassert> #include <cstdio> #include <bits/stdc++.h> using namespace std; void Alice( int n, int m, int A[], int B[] ){ vector<array<int,2>>edges; for(int i = 0;i<m;i++){ edges.push_back({A[i]+12,B[i]+12}); } for(int i = 0;i<n;i++){ int p = i+1; for(int bit = 0;bit<10;bit++){ if((1<<bit)&p) { edges.push_back({bit,i+12}); } } edges.push_back({10,i+12}); } edges.push_back({10,11}); edges.push_back({0,1}); edges.push_back({1,2}); edges.push_back({2,3}); edges.push_back({3,4}); edges.push_back({4,5}); edges.push_back({5,6}); edges.push_back({6,7}); edges.push_back({7,8}); edges.push_back({8,9}); InitG(n+12,edges.size()); for(int i = 0;i<edges.size();i++){ MakeG(i,edges[i][0],edges[i][1]); } }
#include "Boblib.h" #include <cassert> #include <cstdio> #include <bits/stdc++.h> using namespace std; vector<int>leafs; vector<int>ord; void dfs(int st, set<int>g[], set<int>nodes, int par){ ord.push_back(st); bool leaf=1; for(int i : g[st]){ if(nodes.find(i)!=nodes.end()&&i!=par){ dfs(i,g,nodes,st); leaf=0; } } if(leaf){ leafs.push_back(st); } } void Bob( int v, int u, int C[], int D[] ){ int n = v-12; set<int>rg[v]; int deg[v]; fill(deg,deg+v,0); for(int i = 0;i<u;i++){ rg[C[i]].insert(D[i]); rg[D[i]].insert(C[i]); deg[C[i]]++; deg[D[i]]++; } set<int>bitnode; for(int i = 0;i<v;i++){ bitnode.insert(i); } int cov = -1; for(int i = 0;i<v;i++){ if(deg[i]==1){ if(deg[*rg[i].begin()]==n+1){ cov=*rg[i].begin(); break; } } } assert(cov!=-1); for(int i : rg[cov]){ bitnode.erase(i); } bitnode.erase(cov); assert(bitnode.size()==10); leafs.clear(); dfs(*bitnode.begin(), rg, bitnode, -1); if(leafs.size()<2){ assert(leafs.size()==1); leafs.push_back(*bitnode.begin()); } assert(leafs.size()==2); ord.clear(); if(deg[leafs[0]]>deg[leafs[1]]){ dfs(leafs[0],rg,bitnode, -1); } else{ dfs(leafs[1],rg,bitnode, -1); } assert(ord.size()==10); //order obtained vector<array<int,2>>edges; for(int i = 0;i<v;i++){ if(bitnode.find(i)!=bitnode.end()) continue; int ind = 0; for(int b = 0;b<10;b++){ if(rg[i].find(ord[b])!=rg[i].end()){ ind+=(1<<b); } } ind--; for(int j : rg[i]){ if(bitnode.find(j)!=bitnode.end()) continue; int ind2 = 0; for(int b = 0;b<10;b++){ if(rg[j].find(ord[b])!=rg[j].end()){ ind2+=(1<<b); } } ind2--; if(ind<0||ind2<0){ continue; } if(ind>ind2) continue; edges.push_back({ind,ind2}); } } InitMap(n,edges.size()); for(int i = 0;i<edges.size();i++){ MakeMap(edges[i][0],edges[i][1]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...