oj.uz

답안 #199099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199099 2020-01-29T10:27:06 Z godwind 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 92 ms 34552 KB 
#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.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 15 ms 9976 KB Output is correct
3 Correct 11 ms 9976 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 11 ms 9848 KB Output is correct
6 Correct 12 ms 9976 KB Output is correct
7 Correct 12 ms 9848 KB Output is correct
8 Correct 12 ms 9976 KB Output is correct
9 Correct 14 ms 10104 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 15 ms 9976 KB Output is correct
3 Correct 11 ms 9976 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 11 ms 9848 KB Output is correct
6 Correct 12 ms 9976 KB Output is correct
7 Correct 12 ms 9848 KB Output is correct
8 Correct 12 ms 9976 KB Output is correct
9 Correct 14 ms 10104 KB Output is correct
10 Correct 11 ms 9848 KB Output is correct
11 Correct 26 ms 13052 KB Output is correct
12 Correct 49 ms 15064 KB Output is correct
13 Correct 64 ms 23752 KB Output is correct
14 Runtime error 92 ms 34552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 15 ms 9976 KB Output is correct
3 Correct 11 ms 9976 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 11 ms 9848 KB Output is correct
6 Correct 12 ms 9976 KB Output is correct
7 Correct 12 ms 9848 KB Output is correct
8 Correct 12 ms 9976 KB Output is correct
9 Correct 14 ms 10104 KB Output is correct
10 Correct 11 ms 9848 KB Output is correct
11 Correct 26 ms 13052 KB Output is correct
12 Correct 49 ms 15064 KB Output is correct
13 Correct 64 ms 23752 KB Output is correct
14 Runtime error 92 ms 34552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -