oj.uz

Submission #321326

# Submission time Handle Problem Language Result Execution time Memory
321326 2020-11-12T06:00:33 Z ronnith Regions (IOI09_regions) C++14
30 / 100
 1612 ms 131076 KB 
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i = a;i < b;i ++)
#define trav(e,x) for(auto e:x)
#define maxn 200000
#define maxr 5000

using ll = long long;

using namespace std;

ll N, R, Q, region[maxn], ans[maxr][maxr];
vector<ll> adj[maxn];

void dfs(ll x,ll pr,ll crr,ll val)
{
	if(region[x] == crr)val ++;
	ans[crr][region[x]] += val;
	trav(e,adj[x])
	{
		if(e != pr)
		{
			dfs(e,x,crr,val);
		}
	}
}

void preProccess()
{
	FOR(i,0,R)
	{
		dfs(0,-1,i,0);
	}
}

int main()
{
	scanf("%lld%lld%lld",&N,&R,&Q);
	
	ll x,y;
	scanf("%lld",&x);
	region[0] = x - 1;
	FOR(i,0,N - 1)
	{
		scanf("%lld%lld",&x,&y);
		x --;y --;
		adj[i + 1].push_back(x);
		adj[x].push_back(i + 1);
		region[i + 1] = y;
	}
	FOR(i,0,R)
	{
		fill(ans[i],ans[i] + R,0);
	}

	preProccess();

	FOR(i,0,Q)
	{
		scanf("%lld%lld",&x,&y);
		x --;y --;
		printf("%lld\n", ans[x][y]);
		fflush(stdout);
	}

	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  scanf("%lld%lld%lld",&N,&R,&Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |  scanf("%lld",&x);
      |  ~~~~~^~~~~~~~~~~
regions.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5228 KB Output is correct
5 Correct 11 ms 5228 KB Output is correct
6 Correct 22 ms 6636 KB Output is correct
7 Correct 31 ms 5868 KB Output is correct
8 Correct 42 ms 6252 KB Output is correct
9 Correct 71 ms 7404 KB Output is correct
10 Correct 157 ms 8676 KB Output is correct
11 Correct 187 ms 7276 KB Output is correct
12 Correct 255 ms 9580 KB Output is correct
13 Correct 391 ms 8432 KB Output is correct
14 Correct 273 ms 7404 KB Output is correct
15 Correct 250 ms 10596 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1237 ms 10216 KB Output is correct
2 Correct 1612 ms 10084 KB Output is correct
3 Correct 1541 ms 12388 KB Output is correct
4 Runtime error 88 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 86 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 102 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 102 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 117 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 153 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 159 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 159 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 146 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 141 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 168 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 177 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 164 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 183 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)