Submission #199015

#	Time	Username	Problem	Language	Result	Execution time	Memory
199015		godwind	Tropical Garden (IOI11_garden)	C++14	49 / 100	5075 ms	4984 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 = 100 * 1000 + 228;
 
int n, m, p, q;
vector<int> g[MAXN];
 
int go[MAXN], sz[MAXN];
int ans[MAXN];
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n = N;
	m = M;
	q = Q;
	++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;
			}
		}
	}
	int mx = 0;
	for (int i = 0; i < Q; ++i) {
		// uax(mx, G[i]);
		mx = max(mx, G[i]);
	}
	for (int it = 1; it <= n; ++it) {
		int v = it;
		for (int i = 1; i <= mx; ++i) {
			v = go[v];
			if (v == P || v == n + P) {
				++ans[i];
			}
		}
	}
    for (int i = 0; i < Q; i++) {
        answer(ans[G[i]]);
    }
}
 
// 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