Submission #199100

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
199100	2020-01-29T10:27:33 Z	godwind	Tropical Garden (IOI11_garden)	C++14	100 / 100	3100 ms	45504 KB

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 = 400 * 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.0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	19448 KB	Output is correct
2	Correct	18 ms	19320 KB	Output is correct
3	Correct	18 ms	19320 KB	Output is correct
4	Correct	17 ms	19192 KB	Output is correct
5	Correct	17 ms	19192 KB	Output is correct
6	Correct	18 ms	19448 KB	Output is correct
7	Correct	18 ms	19192 KB	Output is correct
8	Correct	18 ms	19320 KB	Output is correct
9	Correct	20 ms	19448 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	19448 KB	Output is correct
2	Correct	18 ms	19320 KB	Output is correct
3	Correct	18 ms	19320 KB	Output is correct
4	Correct	17 ms	19192 KB	Output is correct
5	Correct	17 ms	19192 KB	Output is correct
6	Correct	18 ms	19448 KB	Output is correct
7	Correct	18 ms	19192 KB	Output is correct
8	Correct	18 ms	19320 KB	Output is correct
9	Correct	20 ms	19448 KB	Output is correct
10	Correct	18 ms	19192 KB	Output is correct
11	Correct	35 ms	22264 KB	Output is correct
12	Correct	53 ms	23800 KB	Output is correct
13	Correct	69 ms	32204 KB	Output is correct
14	Correct	182 ms	34040 KB	Output is correct
15	Correct	198 ms	36088 KB	Output is correct
16	Correct	144 ms	31480 KB	Output is correct
17	Correct	133 ms	30076 KB	Output is correct
18	Correct	56 ms	24568 KB	Output is correct
19	Correct	182 ms	35704 KB	Output is correct
20	Correct	201 ms	36028 KB	Output is correct
21	Correct	147 ms	31864 KB	Output is correct
22	Correct	134 ms	30328 KB	Output is correct
23	Correct	192 ms	37752 KB	Output is correct

Subtask #3

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	19448 KB	Output is correct
2	Correct	18 ms	19320 KB	Output is correct
3	Correct	18 ms	19320 KB	Output is correct
4	Correct	17 ms	19192 KB	Output is correct
5	Correct	17 ms	19192 KB	Output is correct
6	Correct	18 ms	19448 KB	Output is correct
7	Correct	18 ms	19192 KB	Output is correct
8	Correct	18 ms	19320 KB	Output is correct
9	Correct	20 ms	19448 KB	Output is correct
10	Correct	18 ms	19192 KB	Output is correct
11	Correct	35 ms	22264 KB	Output is correct
12	Correct	53 ms	23800 KB	Output is correct
13	Correct	69 ms	32204 KB	Output is correct
14	Correct	182 ms	34040 KB	Output is correct
15	Correct	198 ms	36088 KB	Output is correct
16	Correct	144 ms	31480 KB	Output is correct
17	Correct	133 ms	30076 KB	Output is correct
18	Correct	56 ms	24568 KB	Output is correct
19	Correct	182 ms	35704 KB	Output is correct
20	Correct	201 ms	36028 KB	Output is correct
21	Correct	147 ms	31864 KB	Output is correct
22	Correct	134 ms	30328 KB	Output is correct
23	Correct	192 ms	37752 KB	Output is correct
24	Correct	20 ms	19192 KB	Output is correct
25	Correct	122 ms	22652 KB	Output is correct
26	Correct	165 ms	24312 KB	Output is correct
27	Correct	2651 ms	33224 KB	Output is correct
28	Correct	1069 ms	35704 KB	Output is correct
29	Correct	3054 ms	36092 KB	Output is correct
30	Correct	1745 ms	31608 KB	Output is correct
31	Correct	1796 ms	30072 KB	Output is correct
32	Correct	176 ms	24312 KB	Output is correct
33	Correct	1139 ms	35832 KB	Output is correct
34	Correct	3100 ms	36088 KB	Output is correct
35	Correct	1827 ms	31736 KB	Output is correct
36	Correct	1748 ms	30304 KB	Output is correct
37	Correct	837 ms	37884 KB	Output is correct
38	Correct	2360 ms	45504 KB	Output is correct