oj.uz

Submission #62885

# Submission time Handle Problem Language Result Execution time Memory
62885 2018-07-30T16:34:12 Z reality Tropical Garden (IOI11_garden) C++17
100 / 100
 3095 ms 35644 KB 
#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

const int NN = 5e5 + 5;

int f[NN];

int deg[NN];

int Deg[NN];

int was[NN];

int D[NN][2];

vi g[NN];

void dfs(int node,int w) {
	for (auto it : g[node])
		if (D[it][w] == -1) {
			D[it][w] = D[node][w] + 1;
			dfs(it,w);
		}
}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	vector < pii > e;
	int n = N;
	for (int i = 0;i < n + n;++i)
		f[i] = -1;
	for (int i = 0;i < M;++i) {
		int u = R[i][0];
		int v = R[i][1];
		++Deg[u];
		++Deg[v];
		smin(Deg[u],2);
		smin(Deg[v],2);
	}
	for (int i = 0;i < M;++i) {
		int u = R[i][0];
		int v = R[i][1];
		++deg[u];
		++deg[v];
		for (int cs = 0;cs < 2;++cs) {
			if (deg[u] == 1) {
				if (deg[v] >= Deg[v])
					f[u * 2] = v * 2;
				else
					f[u * 2] = v * 2 + 1;
			}
			else
			if (deg[u] == 2) {
				if (deg[v] >= Deg[v])
					f[u * 2 + 1] = v * 2;
				else
					f[u * 2 + 1] = v * 2 + 1;
			}
			swap(u,v);
		}
	}
	for (int i = 0;i < n + n;++i)
		if (f[i] != -1) {
			g[f[i]].pb(i);
		}
	for (int i = 0;i < n + n;++i)
		for (int t = 0;t < 2;++t)
			D[i][t] = -1;
	D[P * 2][0] = 0;
	D[P * 2 + 1][1] = 0;
	dfs(P * 2,0);
	dfs(P * 2 + 1,1);
	int cycle[2] = {-1,-1};
	for (int t = 0;t < 2;++t) {
		int cnt = P * 2 + t;
		for (int i = 0;i < n + n;++i)
			was[i] = 0;
		int vis = 0;
		while (!was[cnt]) {
			++vis;
			was[cnt] = 1;
			cnt = f[cnt];
		}
		if (cnt == P * 2 + t)
			cycle[t] = vis;
	}
	for (int i = 0;i < Q;++i) {
		int ans = 0;
		for (int j = 0;j < n + n;j += 2) {
			int ok = 0;
			for (int t = 0;t < 2;++t) 
				if (D[j][t] != -1) {
					if (G[i] == D[j][t])
						ok = 1;
					else 
					if (cycle[t] != -1) {
						ok |= (D[j][t] <= G[i]) && !((G[i] - D[j][t]) % cycle[t]);
					}
				}
			ans += ok;
		}
		answer(ans);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12284 KB Output is correct
2 Correct 17 ms 12152 KB Output is correct
3 Correct 14 ms 12280 KB Output is correct
4 Correct 7 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 14 ms 12280 KB Output is correct
7 Correct 9 ms 12024 KB Output is correct
8 Correct 13 ms 12152 KB Output is correct
9 Correct 15 ms 12280 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12284 KB Output is correct
2 Correct 17 ms 12152 KB Output is correct
3 Correct 14 ms 12280 KB Output is correct
4 Correct 7 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 14 ms 12280 KB Output is correct
7 Correct 9 ms 12024 KB Output is correct
8 Correct 13 ms 12152 KB Output is correct
9 Correct 15 ms 12280 KB Output is correct
10 Correct 13 ms 12152 KB Output is correct
11 Correct 24 ms 14200 KB Output is correct
12 Correct 37 ms 15476 KB Output is correct
13 Correct 62 ms 29628 KB Output is correct
14 Correct 106 ms 23284 KB Output is correct
15 Correct 124 ms 23416 KB Output is correct
16 Correct 105 ms 20496 KB Output is correct
17 Correct 91 ms 19292 KB Output is correct
18 Correct 48 ms 15608 KB Output is correct
19 Correct 103 ms 23156 KB Output is correct
20 Correct 136 ms 23364 KB Output is correct
21 Correct 106 ms 20400 KB Output is correct
22 Correct 97 ms 19360 KB Output is correct
23 Correct 109 ms 24272 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12284 KB Output is correct
2 Correct 17 ms 12152 KB Output is correct
3 Correct 14 ms 12280 KB Output is correct
4 Correct 7 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 14 ms 12280 KB Output is correct
7 Correct 9 ms 12024 KB Output is correct
8 Correct 13 ms 12152 KB Output is correct
9 Correct 15 ms 12280 KB Output is correct
10 Correct 13 ms 12152 KB Output is correct
11 Correct 24 ms 14200 KB Output is correct
12 Correct 37 ms 15476 KB Output is correct
13 Correct 62 ms 29628 KB Output is correct
14 Correct 106 ms 23284 KB Output is correct
15 Correct 124 ms 23416 KB Output is correct
16 Correct 105 ms 20496 KB Output is correct
17 Correct 91 ms 19292 KB Output is correct
18 Correct 48 ms 15608 KB Output is correct
19 Correct 103 ms 23156 KB Output is correct
20 Correct 136 ms 23364 KB Output is correct
21 Correct 106 ms 20400 KB Output is correct
22 Correct 97 ms 19360 KB Output is correct
23 Correct 109 ms 24272 KB Output is correct
24 Correct 14 ms 12104 KB Output is correct
25 Correct 163 ms 14344 KB Output is correct
26 Correct 231 ms 15652 KB Output is correct
27 Correct 1715 ms 29628 KB Output is correct
28 Correct 1513 ms 23096 KB Output is correct
29 Correct 1987 ms 23316 KB Output is correct
30 Correct 1267 ms 20536 KB Output is correct
31 Correct 1065 ms 19204 KB Output is correct
32 Correct 248 ms 15664 KB Output is correct
33 Correct 1520 ms 23352 KB Output is correct
34 Correct 1897 ms 23552 KB Output is correct
35 Correct 1242 ms 20164 KB Output is correct
36 Correct 1674 ms 19132 KB Output is correct
37 Correct 1205 ms 24708 KB Output is correct
38 Correct 3095 ms 35644 KB Output is correct