Submission #1250170

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