oj.uz

Submission #199015

# Submission time Handle Problem Language Result Execution time Memory
199015 2020-01-28T16:21:33 Z godwind Tropical Garden (IOI11_garden) C++14
49 / 100
 5000 ms 4984 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 = 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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB Output is correct
2 Correct 7 ms 2680 KB Output is correct
3 Correct 8 ms 2808 KB Output is correct
4 Correct 7 ms 2680 KB Output is correct
5 Correct 7 ms 2680 KB Output is correct
6 Correct 8 ms 2808 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 10 ms 2936 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB Output is correct
2 Correct 7 ms 2680 KB Output is correct
3 Correct 8 ms 2808 KB Output is correct
4 Correct 7 ms 2680 KB Output is correct
5 Correct 7 ms 2680 KB Output is correct
6 Correct 8 ms 2808 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 10 ms 2936 KB Output is correct
10 Correct 9 ms 2680 KB Output is correct
11 Execution timed out 5075 ms 4984 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB Output is correct
2 Correct 7 ms 2680 KB Output is correct
3 Correct 8 ms 2808 KB Output is correct
4 Correct 7 ms 2680 KB Output is correct
5 Correct 7 ms 2680 KB Output is correct
6 Correct 8 ms 2808 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 10 ms 2936 KB Output is correct
10 Correct 9 ms 2680 KB Output is correct
11 Execution timed out 5075 ms 4984 KB Time limit exceeded
12 Halted 0 ms 0 KB -