Submission #1260212

#TimeUsernameProblemLanguageResultExecution timeMemory
1260212software1146세계 지도 (IOI25_worldmap)C++17
100 / 100
21 ms2888 KiB
#include "worldmap.h" #include <bits/stdc++.h> using namespace std; void dfs(int st, vector<int>g[], bool vis[], vector<vector<int>> &ans, int &sm, int n){ vis[st]=1; vector<int>anc; for(int i : g[st]){ if(vis[i]){ anc.push_back(i); } } for(int i = 0;i<=sm;i++){ int j = sm-i; if(i>=n||j>=n) continue; ans[i][j]=st; } sm++; if(anc.size()){ int in = 0; for(int i = 0;i<=sm;i++){ int j = sm-i; if(i>=n||j>=n) continue; ans[i][j]=anc[min(in,(int)anc.size()-1)]; in++; } sm++; for(int i = 0;i<=sm;i++){ int j = sm-i; if(i>=n||j>=n) continue; ans[i][j]=st; } sm++; } for(int i : g[st]){ if(vis[i]) continue; dfs(i,g,vis,ans,sm,n); for(int i = 0;i<=sm;i++){ int j = sm-i; if(i>=n||j>=n) continue; ans[i][j]=st; } sm++; } } vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) { vector<int>g[n]; for(int i = 0;i<m;i++){ A[i]--; B[i]--; g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); } bool vis[n]; fill(vis,vis+n,0); vector<vector<int>>ans(2*n-1,vector<int>(2*n-1,-1)); int t = 0; dfs(0,g,vis,ans,t,2*n-1); for(int i = 0;i<2*n-1;i++){ for(int j = 0;j<2*n-1;j++){ ans[i][j]++; } } 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...