oj.uz

Submission #124773

# Submission time Handle Problem Language Result Execution time Memory
124773 2019-07-03T22:30:18 Z arthurconmy Regions (IOI09_regions) C++14
12 / 100
 8000 ms 18112 KB 
// check ctrl+v :^)
/* Arthur Conmy IOI template - minimal! */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
#define pb push_back
#define ff first
#define ss second
#define REP(i,a,b) \
for(int i = int(a); i<=int(b); i++)

const int MAXN=int(2e5)+1;

int reg[MAXN];
bool vis[MAXN];
vi adj[MAXN];
ll ans=0;
ll cur_r1=0;
int r1,r2;

void dfs(int v)
{
	if(reg[v]==r1) cur_r1++;
	if(reg[v]==r2) ans+=cur_r1;

	for(auto u:adj[v])
	{
		if(vis[u]) continue;
		vis[u]=1;
		dfs(u);
	}

	if(reg[v]==r1) cur_r1--;
}

int main()
{
	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	int n,r,q;
	cin>>n>>r>>q;

	int h1;
	cin>>h1;

	reg[1]=h1;

	REP(i,2,n)
	{
		int s,h;
		cin>>s>>h;

		adj[s].pb(i);
		adj[i].pb(s);
		reg[i]=h;
	}

	REP(QUERY,1,q)
	{
		// int r1,r2;
		cin>>r1>>r2;

		vis[1]=1;
		dfs(1);

		cout << ans << endl;

		REP(i,0,MAXN-1) vis[i]=0;
		ans=0;
		cur_r1=0;
	}
}

Subtask #1
12.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5136 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 27 ms 5112 KB Output is correct
4 Correct 53 ms 5160 KB Output is correct
5 Correct 91 ms 5240 KB Output is correct
6 Correct 237 ms 5240 KB Output is correct
7 Correct 409 ms 5240 KB Output is correct
8 Correct 515 ms 5240 KB Output is correct
9 Correct 843 ms 5496 KB Output is correct
10 Correct 3375 ms 5752 KB Output is correct
11 Correct 6081 ms 5756 KB Output is correct
12 Correct 7549 ms 6008 KB Output is correct
13 Execution timed out 8025 ms 6008 KB Time limit exceeded
14 Execution timed out 8098 ms 6264 KB Time limit exceeded
15 Execution timed out 8051 ms 7800 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8064 ms 8312 KB Time limit exceeded
2 Execution timed out 8068 ms 8056 KB Time limit exceeded
3 Execution timed out 8010 ms 9496 KB Time limit exceeded
4 Execution timed out 8077 ms 6292 KB Time limit exceeded
5 Execution timed out 8018 ms 7288 KB Time limit exceeded
6 Execution timed out 8098 ms 7292 KB Time limit exceeded
7 Execution timed out 8042 ms 7800 KB Time limit exceeded
8 Execution timed out 8064 ms 10744 KB Time limit exceeded
9 Execution timed out 8077 ms 11128 KB Time limit exceeded
10 Execution timed out 8055 ms 13932 KB Time limit exceeded
11 Execution timed out 8021 ms 12604 KB Time limit exceeded
12 Execution timed out 8028 ms 11980 KB Time limit exceeded
13 Execution timed out 8025 ms 12596 KB Time limit exceeded
14 Execution timed out 8016 ms 12500 KB Time limit exceeded
15 Execution timed out 8061 ms 14328 KB Time limit exceeded
16 Execution timed out 8057 ms 18112 KB Time limit exceeded
17 Execution timed out 8061 ms 17424 KB Time limit exceeded