Submission #1249844

#TimeUsernameProblemLanguageResultExecution timeMemory
1249844canadavid1World Map (IOI25_worldmap)C++20
100 / 100
24 ms2888 KiB
/* 4 pixels per connection fold over: dfs tree: very deep,edges go only upwards (num bounded by #nodes below) centroid -> use max height N diagonals interesting (almost double the N) */ #include <iostream> #include <cstdlib> #include "worldmap.h" std::vector<std::vector<int>> try_solve(int N, int M,std::vector<int> A, std::vector<int> B, int K) { std::vector<std::vector<int>> o(K,std::vector<int>(K)); std::vector<std::vector<int>> neigh(N+1); for(int i = 0; i < M; i++) { neigh[A[i]].push_back(B[i]); neigh[B[i]].push_back(A[i]); } int x = 0; std::vector<int> par(N+1); std::vector<int> seen(N+1,0); auto outp = [&](int v) { for(int i = 0; i < K; i++) if(0 <= x-i && x-i < K) o[i][x-i] = v; x++; }; auto dfs = [&](auto self,int w,int pr=-1,int d=1) -> bool { if(w == 0) { std::cerr << "whaaat\n"; } int h = 1; std::vector<int> ex; std::vector<int> ot; if (seen[w]) return false; seen[w] = d; for(auto i : neigh[w]) { if (i == pr) continue; if(seen[i] && seen[i] < d-1) { ex.push_back(i); continue; } if (seen[i]) continue; // o.emplace_back(1,w); ot.emplace_back(i); // self(self,i,w,d+1); } bool done_ex = ex.size() == 0; auto do_ex = [&](){ if (done_ex) return; done_ex = true; while (ex.size()) { for(int i = 0; i < K; i++) { if (0 > x-i || x-i >= K) continue; if(ex.size() == 0) ex.push_back(w); o[i][x-i] = ex.back(); ex.pop_back(); } x++; if (x >= 2*K) { o.clear(); return; }; outp(w); } }; outp(w); for(auto i : ot) { // if (x >= K/2) do_ex(); if (self(self,i,w,d+1)) outp(w); if (x >= 2*K) { o.clear(); return false; }; } do_ex(); return true; // o.emplace_back(1,w); // if (ex.size()) // { // std::vector<int> a(K,w); // for(int i = 0; i < ex.size(); i++) a[2*i] = ex[i]; // o.push_back(std::move(ex)); // o.emplace_back(K,w); // } }; dfs(dfs,1); while(x < 2*K) outp(1); return o; } std::vector<std::vector<int>> create_map(int N, int M,std::vector<int> A, std::vector<int> B) { // st2 for(int K = N; ; K += N/2) { auto o = try_solve(N,M,A,B,K); if (o.size()) return o; } }
#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...