답안 #62885 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62885	2018-07-30T16:34:12 Z	reality	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	3095 ms	35644 KB

garden

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #62885

Compilation message

Subtask #1 49.0 / 49.0

Subtask #2 20.0 / 20.0

Subtask #3 31.0 / 31.0

Subtask #1
49.0 / 49.0

Subtask #2
20.0 / 20.0

Subtask #3
31.0 / 31.0