Submission #1250420

#TimeUsernameProblemLanguageResultExecution timeMemory
1250420bronze_coderWorld Map (IOI25_worldmap)C++20
86 / 100
42 ms5512 KiB
#include "worldmap.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b){ vector<int> visited(n,0); vector<int> q = {0}; int index = 0; visited[0] = 1; for(int i=0;i<m;i++){ a[i]--; b[i]--; } vector<vector<int>> adj(n); for(int i=0;i<m;i++){ adj[a[i]].push_back(b[i]); adj[b[i]].push_back(a[i]); } vector<int> parent(n,-1); while(index<q.size()){ int i = q[index]; for(int j:adj[i]){ if(visited[j]==0){ visited[j] = 1; parent[j] = i; q.push_back(j); } } index++; } vector<vector<int>> adj1(n); for(int i=1;i<n;i++){ adj1[parent[i]].push_back(i); } vector<int> s = {0}; vector<int> visited1(n,0); visited1[0] = 1; vector<int> order; int p[n]; while(s.size()>0){ int i = s[s.size()-1]; if(visited1[i]==2){ s.pop_back(); if(i!=0){ order.push_back(parent[i]); } } if(visited1[i]==1){ p[i] = order.size(); order.push_back(i); for(int j:adj1[i]){ s.push_back(j); visited1[j] = 1; } visited1[i] = 2; } } vector<vector<int>> ans; for(int i=0;i<3*n;i++){ vector<int> v(3*n,order[order.size()-1]+1); ans.push_back(v); } int loc[n][2]; int z = 0; int x = 0; for(int i=0;i<order.size();i++){ if(p[order[i]]==i){ for(int j=0;j<3*n;j++){ if(j<n){ ans[z+x][j] = order[i]+1; } else{ ans[z+1-x][j] = order[i]+1; } } if(x==0){ for(int j=0;j<n;j++){ ans[z+2][j] = order[i]+1; ans[z+1][j] = order[i]+1; } } else{ for(int j=n;j<3*n;j++){ ans[z+2][j] = order[i]+1; ans[z+1][j] = order[i]+1; } } loc[order[i]][0] = z+1; if(x==0){ loc[order[i]][1] = 0; } else{ loc[order[i]][1] = n; } z += 2; x = 1-x; } else{ for(int j=0;j<3*n;j++){ if(j<n){ ans[z+x][j] = order[i]+1; } else{ ans[z+1-x][j] = order[i]+1; } } z += 1; } } vector<int> count(3*n,0); for(int i=0;i<m;i++){ if((a[i]-b[i]+n)%n>n/2){ swap(a[i],b[i]); } ans[loc[a[i]][0]][loc[a[i]][1]+2*count[a[i]]] = b[i]+1; count[a[i]]++; } return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...