Submission #1279861

#TimeUsernameProblemLanguageResultExecution timeMemory
1279861AndreyWorld Map (IOI25_worldmap)C++20
0 / 100
2 ms576 KiB
#include "worldmap.h" #include<bits/stdc++.h> using namespace std; int n; int m; int k; vector<int> haha[100]; vector<int> st(100); vector<vector<int>> ans(0); vector<int> tree[100]; vector<int> banana[100]; vector<int> dep(100); vector<bool> bruh(100); void reset() { for(int i = 0; i < 100; i++) { haha[i].clear(); tree[i].clear(); banana[i].clear(); bruh[i] = true; dep[i] = -1; } ans.clear(); } void dfs(int a, int d) { st[a] = 1; dep[a] = d; bruh[a] = false; for(int v: haha[a]) { if(bruh[v]) { tree[a].push_back(v); dfs(v,d+1); st[a]+=st[v]; } else if(dep[v] > dep[a]) { banana[a].push_back(v); } } } void no(int i, int y, int c) { for(int j = y; j < k; j++) { ans[j][i] = c; } } void dude(int x, int y, int a, int w) { if(st[a] == 1) { for(int i = y; i < k; i++) { for(int j = x; j < x+w; j++) { ans[i][j] = a; } } return; } for(int i = 0; i < 2; i++) { for(int j = x; j < x+w; j++) { ans[y+i][j] = a; } } no(x,y,a); int z = x+1; for(int v: tree[a]) { dude(z,y+2,v,st[v]*2-1); z+=st[v]*2; no(z-1,y,a); } int c = x+1; if(c%2) { c++; } int q = 0; for(int i = c; i < x+w-1; i+=2) { ans[y+2][i] = a; if(q < banana[a].size()) { ans[y+1][i] = banana[a][q]; q++; } } } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { reset(); n = N; m = M; for(int i = 0; i < m; i++) { haha[A[i]].push_back(B[i]); haha[B[i]].push_back(A[i]); } k = 2*n-1; for(int i = 0; i < k; i++) { ans.push_back(vector<int> (k)); } dfs(1,0); dude(0,0,1,k); 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...