oj.uz

Submission #80001

# Submission time Handle Problem Language Result Execution time Memory
80001 2018-10-18T05:40:10 Z Just_Solve_The_Problem Tropical Garden (IOI11_garden) C++11
49 / 100
 5000 ms 4776 KB 
#include "garden.h"
#include "gardenlib.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

const int NN = (int)150007;

int deg[NN];
int n, m, p, q;
vector < int > gr[NN];
int K;

int solve(int v) {
	int k = K;
	int pr = v;
	while (k--) {
		if (gr[v][0] == pr) {
			if (gr[v].size() > 1) {
				pr = v;
				v = gr[v][1];
			} else {
				pr = v;
				v = gr[v][0];
			}
		} else {
			pr = v;
			v = gr[v][0];
		}
	}
	return v == p;
}

void count_routes(int _N, int _M, int _P, int R[][2], int _Q, int G[]) {
	n = _N; m = _M; p = _P;
	for (int i = 0; i < m; i++) {
		if (deg[R[i][0]] != 2) {
			gr[R[i][0]].push_back(R[i][1]);
			deg[R[i][0]]++;
		} 
		if (deg[R[i][1]] != 2) {
			gr[R[i][1]].push_back(R[i][0]);
			deg[R[i][1]]++;
		}
	}
	for (int j = 0; j < _Q; j++) {
		int ans = 0;
		K = G[j];
		for (int i = 0; i < n; i++) {
			ans += solve(i);
		}
		answer(ans);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3832 KB Output is correct
2 Correct 6 ms 3832 KB Output is correct
3 Correct 6 ms 3864 KB Output is correct
4 Correct 5 ms 3804 KB Output is correct
5 Correct 5 ms 3804 KB Output is correct
6 Correct 6 ms 3832 KB Output is correct
7 Correct 5 ms 3804 KB Output is correct
8 Correct 6 ms 3880 KB Output is correct
9 Correct 7 ms 3960 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3832 KB Output is correct
2 Correct 6 ms 3832 KB Output is correct
3 Correct 6 ms 3864 KB Output is correct
4 Correct 5 ms 3804 KB Output is correct
5 Correct 5 ms 3804 KB Output is correct
6 Correct 6 ms 3832 KB Output is correct
7 Correct 5 ms 3804 KB Output is correct
8 Correct 6 ms 3880 KB Output is correct
9 Correct 7 ms 3960 KB Output is correct
10 Correct 10 ms 3832 KB Output is correct
11 Execution timed out 5042 ms 4776 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3832 KB Output is correct
2 Correct 6 ms 3832 KB Output is correct
3 Correct 6 ms 3864 KB Output is correct
4 Correct 5 ms 3804 KB Output is correct
5 Correct 5 ms 3804 KB Output is correct
6 Correct 6 ms 3832 KB Output is correct
7 Correct 5 ms 3804 KB Output is correct
8 Correct 6 ms 3880 KB Output is correct
9 Correct 7 ms 3960 KB Output is correct
10 Correct 10 ms 3832 KB Output is correct
11 Execution timed out 5042 ms 4776 KB Time limit exceeded
12 Halted 0 ms 0 KB -