Submission #1250183

#TimeUsernameProblemLanguageResultExecution timeMemory
1250183bronze_coderWorld Map (IOI25_worldmap)C++20
15 / 100
54 ms7532 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; int loc[n]; int z = 0; for(int i=0;i<order.size();i++){ vector<int> v(4*n-1,order[i]+1); if(p[order[i]]==i){ loc[order[i]] = z+1; z += 3; ans.push_back(v); ans.push_back(v); ans.push_back(v); } else{ z += 1; ans.push_back(v); } } vector<int> count(3*n,0); for(int i=0;i<m;i++){ ans[loc[a[i]]][2*count[a[i]]] = b[i]+1; count[p[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...