oj.uz

Submission #302811

# Submission time Handle Problem Language Result Execution time Memory
302811 2020-09-19T08:48:54 Z BlancaHM Regions (IOI09_regions) C++14
14 / 100
 8000 ms 21612 KB 
#include <iostream>
#include <fstream>
#include <cfloat>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>
#include <cmath>
#include <climits>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vvvl> vvvvl;
typedef vector<string> vs;
#define fir first
#define sec second
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define len(v) ((int)v.size())
#define all(v) v.begin(), v.end()

vi country;
vvi G;
int N, R, e1, e2, ans;

int dfs(int S) {
	int cur = 0;
	for (auto v: G[S]) {
		cur += dfs(v);
		if (country[v] == e2) cur++;
	}
	if (country[S] == e1) ans += cur;
	return cur;
}

int main() {
	int Q, cn, sup;
	scanf("%d %d %d", &N, &R, &Q);
	G.assign(N, vi());
	country = vi(N);
	cin >> cn;
	country[0] = cn;
	map<pii, int> past;
	for (int i = 1; i < N; i++) {
		scanf("%d %d", &sup, &cn);
		G[sup-1].push_back(i);
		country[i] = cn;
	}
	while(Q--) {
		scanf("%d %d", &e1, &e2);
		if (past.find(mp(e1, e2)) != past.end()) {
			printf("%d\n", past[mp(e1, e2)]);
			fflush(stdout);
			continue;
		}
		ans = 0;
		dfs(0);
		printf("%d\n", ans);
		fflush(stdout);
		past[mp(e1, e2)] = ans;
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  scanf("%d %d %d", &N, &R, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%d %d", &sup, &cn);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d %d", &e1, &e2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 11 ms 384 KB Output is correct
6 Correct 34 ms 504 KB Output is correct
7 Correct 100 ms 508 KB Output is correct
8 Correct 134 ms 664 KB Output is correct
9 Correct 262 ms 1272 KB Output is correct
10 Correct 1836 ms 1372 KB Output is correct
11 Correct 3612 ms 1908 KB Output is correct
12 Correct 3953 ms 2640 KB Output is correct
13 Correct 7562 ms 2132 KB Output is correct
14 Execution timed out 8003 ms 3052 KB Time limit exceeded
15 Correct 6073 ms 5696 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8055 ms 5680 KB Time limit exceeded
2 Execution timed out 8090 ms 4592 KB Time limit exceeded
3 Execution timed out 8066 ms 7832 KB Time limit exceeded
4 Execution timed out 8086 ms 2584 KB Time limit exceeded
5 Execution timed out 8064 ms 5492 KB Time limit exceeded
6 Execution timed out 8036 ms 4176 KB Time limit exceeded
7 Execution timed out 8039 ms 4980 KB Time limit exceeded
8 Execution timed out 8019 ms 10324 KB Time limit exceeded
9 Execution timed out 8086 ms 10184 KB Time limit exceeded
10 Execution timed out 8042 ms 15296 KB Time limit exceeded
11 Execution timed out 8012 ms 9980 KB Time limit exceeded
12 Execution timed out 8034 ms 11852 KB Time limit exceeded
13 Execution timed out 8048 ms 12060 KB Time limit exceeded
14 Execution timed out 8013 ms 11628 KB Time limit exceeded
15 Execution timed out 8080 ms 15916 KB Time limit exceeded
16 Execution timed out 8057 ms 21612 KB Time limit exceeded
17 Execution timed out 8045 ms 20408 KB Time limit exceeded