제출 #551212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551212		Keshi	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	130 ms	52636 KiB

garden

//In the name of God
#include "garden.h"
#include "gardenlib.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 7;
const ll INF = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll pw(ll a, ll b){
	ll c = 1;
	while(b){
		if(b & 1) c = c * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return c;
}

int n, a[maxn], dis[maxn];
int cnt[2][maxn], dor[2];
bool vis[maxn];
vector<int> g[maxn], gp[maxn];

void dfs(int v){
	vis[v] = 1;
	for(int u : gp[v]){
		if(vis[u]) continue;
		dis[u] = dis[v] + 1;
		dfs(u);
	}
	return;
}

void Do(int x, int f){
	memset(dis, -1, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[x] = 0;
	dfs(x);
	for(int i = 0; i < (n << 1); i += 2){
		if(~dis[i]) cnt[f][dis[i]]++;
	}
	dor[f] = -1;
	if(dis[a[x]] == -1) return;
	int t = dis[a[x]] + 1;
	dor[f] = t;
	for(int i = t; i < maxn; i++){
		cnt[f][i] += cnt[f][i - t];
	}
	return;
}

void count_routes(int N, int m, int p, int R[][2], int Q, int G[]){
	n = N;
	for(int i = 0; i < m; i++){
		int v = R[i][0], u = R[i][1];
		g[v].pb(u);
		g[u].pb(v);
	}
	for(int i = 0; i < n; i++){
		int v = g[i][0];
		if(g[v][0] == i) a[i << 1] = (v << 1) | 1;
		else a[i << 1] = v << 1;
		if(Sz(g[i]) == 1){
			a[i << 1 | 1] = a[i << 1];
			continue;
		}
		v = g[i][1];
		if(g[v][0] == i) a[i << 1 | 1] = (v << 1) | 1;
		else a[i << 1 | 1] = v << 1;
	}
	for(int i = 0; i < (n << 1); i++){
		gp[a[i]].pb(i);
	}
	Do(p << 1, 0);
	Do(p << 1 | 1, 1);
	for(int i = 0; i < Q; i++){
		int x = G[i];
		int ans = 0;
		if(dor[0] == -1){
			if(x < maxn) ans += cnt[0][x];
		}
		else{
			if(x >= maxn) x = (maxn - (maxn % dor[0])) + (dor[0] << 2) + (x % dor[0]);
			while(x >= maxn) x -= dor[0];
			ans += cnt[0][x];
		}
		x = G[i];
		if(dor[1] == -1){
			if(x < maxn) ans += cnt[1][x];
		}
		else{
			if(x >= maxn) x = (maxn - (maxn % dor[1])) + (dor[1] << 2) + (x % dor[1]);
			while(x >= maxn) x -= dor[1];
			ans += cnt[1][x];
		}
		answer(ans);
	}
	return;
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31