Submission #199099

#	Time	Username	Problem	Language	Result	Execution time	Memory
199099		godwind	Tropical Garden (IOI11_garden)	C++14	49 / 100	92 ms	34552 KiB

garden

#include "gardenlib.h"
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
// #include "grader.h"

using namespace std;

// void answer(int i) {
// 	cout << i << '\n';
// }

const int MAXN = 200 * 1000 + 228;

int n, m, p, q;
vector<int> g[MAXN];

int go[MAXN], sz[MAXN];
int ans[MAXN];
bool in_cycle[MAXN], used[MAXN], was[MAXN];

vector<int> cycle[MAXN];
int num[MAXN], ind[MAXN];
int h[MAXN], tin[MAXN], tout[MAXN], timer = 0;
int dist1[MAXN], dist2[MAXN];
int parent[MAXN];

void dfs(int v, int par, int gpar) {
	parent[v] = gpar;
	h[v] = (par == v ? 0 : h[par] + 1);
	tin[v] = timer++;
	for (int to : g[v]) {
		if (in_cycle[to]) continue;
		dfs(to, v, gpar);
	}
	tout[v] = timer++;
}
bool anc(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int get_dist(int v, int p) {
	if (anc(p, v)) {
		return h[v] - h[p];
	}
	int cur = 0;
	if (in_cycle[p]) {
		if (!in_cycle[v]) {
			cur = h[v];
			v = parent[v];
		}
		if (num[p] != num[v]) return -1;
		if (ind[v] < ind[p]) cur += ind[p] - ind[v];
		else cur += (int)cycle[num[p]].size() - ind[v] + ind[p];
	} else return -1;
	return cur;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n = N;
	m = M;
	q = Q;
	++P;
	p = P;
	for (int i = 0; i < m; ++i) {
		++R[i][0], ++R[i][1];
		g[R[i][0]].push_back(R[i][1]);
		g[R[i][1]].push_back(R[i][0]);
	}
	for (int i = 1; i <= n; ++i) {
		sz[i] = (int)g[i].size();
	}
	for (int i = 1; i <= n; ++i) {
		int to = g[i][0];
		if (g[to][0] == i && sz[to] > 1) {
			go[i] = to + n;
			if (sz[i] == 1) go[i + n] = to + n;
		} else {
			go[i] = to;
			if (sz[i] == 1) go[i + n] = to + n;
		}

		if (sz[i] != 1) {
			to = g[i][1];
			if (g[to][0] == i && sz[to] > 1) {
				go[n + i] = to + n;
			} else {
				go[n + i] = to;
			}
		}
	}
	for (int i = 1; i <= 2 * n; ++i) {
		g[i].clear();
	}
	for (int i = 1; i <= 2 * n; ++i) {
		g[go[i]].push_back(i);
	}
	int ptr = 0;
	for (int i = 1; i <= 2 * n; ++i) {
		vector<int> vvs;
		int v = i;
		was[v] = 1;
		bool found = 0;
		vvs.push_back(v);
		while (!used[v]) {
			used[v] = 1;
			v = go[v];
			vvs.push_back(v);
			if (was[v]) {
				found = 1;
				break;
			}
			was[v] = 1;
		}
		for (int x : vvs) {
			was[x] = 0;
		}
		if (found) {
			++ptr;
			int s = v;
			do
			{
				cycle[ptr].push_back(v);
				num[v] = ptr;
				ind[v] = (int)cycle[ptr].size() - 1;
				in_cycle[v] = 1;
				v = go[v];
			}
			while(v != s);
		}
	}
	for (int i = 1; i <= 2 * n; ++i) {
		if (in_cycle[i]) {
			dfs(i, i, i);
		}
	}
	get_dist(1, P + n);
	for (int v = 1; v <= n; ++v) {
		dist1[v] = get_dist(v, P);
		dist2[v] = get_dist(v, P + n);
	}
	int SZ1 = 0, SZ2 = 0;
	if (in_cycle[P]) SZ1 = (int)cycle[num[P]].size();
	if (in_cycle[n + P]) SZ2 = (int)cycle[num[n + P]].size();
    for (int i = 0; i < Q; i++) {
    	bool ok = 0;
    	int k = G[i];
    	int ans = 0;
    	for (int v = 1; v <= n; ++v) {
    		ok = 0;
    		if (dist1[v] != -1) {
    			if (dist1[v] <= k) {
    				if (dist1[v] == k) ok = 1;
    				else if (in_cycle[P] && (k - dist1[v]) % SZ1 == 0) {
    					ok = 1;
    				}
    			}
    		}
    		if (!ok && dist2[v] != -1) {
    			if (dist2[v] <= k) {
    				if (dist2[v] == k) ok = 1;
    				else if (in_cycle[n + P] && (k - dist2[v]) % SZ2 == 0) {
    					ok = 1;
    				}
    			}
    		}
    		if (ok) {
    			++ans;
    		}
    	}
    	answer(ans);
    }
}

// int G[100];
// int R[100][2];

// signed main() {
// 	cin >> n >> m >> p;
// 	for (int i = 0; i < m; ++i) {
// 		cin >> R[i][0] >> R[i][1];
// 	}
// 	cin >> q;
// 	for (int i = 0; i < q; ++i) {
// 		cin >> G[i];
// 	}

// 	count_routes(n, m, p, R, q, G);
// }

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