Submission #1256375

#TimeUsernameProblemLanguageResultExecution timeMemory
1256375WeIlIaNWorld Map (IOI25_worldmap)C++20
15 / 100
15 ms2116 KiB
#include "worldmap.h" #include <bits/stdc++.h> using namespace std; #define MOD1 1000000007 #define MOD2 998244353 #define fir first #define sec second #define pushf push_front #define pushb push_back #define popf pop_front #define popb pop_back #define mp make_pair #define all(a) a.begin(), a.end() #define FOR1(a) for (int _ = 0; _ < a; ++_) #define FOR2(i, a) for (int i = 0; i < a; ++i) #define FOR3(i, a, b) for (int i = a; i < b; ++i) #define RFOR1(a) for (int _ = (a)-1; _ >= 0; --_) #define RFOR2(i, a) for (int i = (a)-1; i >= 0; --i) #define RFOR3(i, a, b) for (int i = (b)-1; i >= a; --i) #define overload3(a, b, c, d, ...) d // Always choose the fourth argument to call. Hence, which function to call is determined by the number of given arguments. #define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__) #define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<string> vs; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef vector<vb> vvb; typedef vector<vc> vvc; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; typedef queue<int> qi; typedef queue<ll> qll; typedef queue<pii> qpii; typedef queue<pll> qpll; typedef deque<int> dqi; typedef deque<ll> dqll; typedef deque<pii> dqpii; typedef deque<pll> dqpll; typedef priority_queue<int> pqi; typedef priority_queue<ll> pqll; typedef priority_queue<pii> pqpii; typedef priority_queue<pll> pqpll; typedef priority_queue<int, vi, greater<int> > r_pqi; typedef priority_queue<ll, vll, greater<ll> > r_pqll; typedef priority_queue<pii, vpii, greater<pii> > r_pqpii; typedef priority_queue<pll, vpll, greater<pll> > r_pqpll; vi seq; vb vis; vi pos; vvi adj; vpii unused; void dfs(int u, int p) { vis[u] = true; seq.pushb(u); pos[u] = seq.size(); seq.pushb(u); seq.pushb(u); int l = adj[u].size(); REP(i, l) { int v = adj[u][i]; if(v == p) { continue; } if(vis[v]) { if(u < v) { unused.pushb(mp(u, v)); } continue; } dfs(v, u); seq.pushb(u); } } vvi create_map(int n, int m, vi A, vi B) { adj = vvi(n+1); vis = vb(n+1); pos = vi(n+1); seq.clear(); unused.clear(); REP(i, m) { adj[A[i]].pushb(B[i]); adj[B[i]].pushb(A[i]); } dfs(1, 0); int h = seq.size(); vvi ans(2*n, vi(2*n, 0)); REP(i, h) { REP(j, max(0, i-2*n+1), min(i+1, 2*n)) { ans[i-j][j] = seq[i]; } } vi cur(n+1), lim(n+1); REP(i, 1, n+1) { cur[i] = (pos[i] > 2 * n ? 4 * n - pos[i] - 2: pos[i]); //cerr<<cur[i]<<' '; } // cerr<<endl; REP(i, unused.size()) { auto [a, b] = unused[i]; if(cur[a] >= cur[b]) { if(pos[a] > 2 * n) { int c = 2 * n - cur[a] - 1; ans[c][pos[a]-c] = b; } else { ans[pos[a]-cur[a]][cur[a]] = b; } cur[a]--; } else { if(pos[b] > 2 * n) { int c = 2 * n - cur[b] - 1; ans[c][pos[b]-c] = a; } else { ans[pos[b]-cur[b]][cur[b]] = a; } cur[b]--; } } 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...