Submission #1256396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256396		WeIlIaN	World Map (IOI25_worldmap)	C++20	15 / 100	15 ms	2120 KiB

worldmap

#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];
		}
	}
	// REP(i, unused.size()) {
	// 	cerr<<unused[i].fir<<' '<<unused[i].sec<<endl;
	// }
	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<<i<<' '<<pos[i]<<' '<<cur[i]<<endl;
	}
	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];
				//cerr<<c<<' '<<pos[a]-c<<endl; 
				ans[c][pos[a]-c] = b;
			}
			else {
				//cerr<<pos[a]-cur[a]<<' '<<cur[a]<<endl;
				ans[pos[a]-cur[a]][cur[a]] = b;
			}
			cur[a]--;
		}
		else {
			if(pos[b] > 2 * n) {
				int c = 2 * n - cur[b] - 1;
				//cerr<<c<<' '<<pos[b]-c<<endl;
				ans[c][pos[b]-c] = a;
			}
			else {
				//cerr<<pos[b]-cur[b]<<' '<<cur[b]<<endl;
				ans[pos[b]-cur[b]][cur[b]] = a;
			}
			cur[b]--;
		}
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56