| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94300 |
2019-01-17T11:57:48 Z |
ekrem |
Regions (IOI09_regions) |
C++ |
|
958 ms |
33728 KB |
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 200005
#define M 25005
#define kok 500
using namespace std;
typedef pair < int , int > ii;
typedef pair < int , ii > iii;
int n, m, q, k, tme, a[N], ne[N], say[N], mi[N], ust[N/kok + 10][M], alt[N/kok + 10][M];
vector < int > g[N];
vector < ii > gez[N];
void bul(int node){
say[mi[a[node]]]++;
for(int i = 1; i <= k; i++)
alt[i][a[node]] += say[i];
for(int i = 0; i < g[node].size(); i++)
bul(g[node][i]);
say[mi[a[node]]]--;
}
void bul2(int node){
say[a[node]]++;
if(mi[a[node]]){
for(int i = 1; i <= m; i++)
ust[mi[a[node]]][i] += say[i];
}
for(int i = 0; i < g[node].size(); i++)
bul2(g[node][i]);
say[a[node]]--;
}
void dfs(int node){
gez[a[node]].pb(mp(++tme, 1));
for(int i = 0; i < g[node].size(); i++)
dfs(g[node][i]);
gez[a[node]].pb(mp(++tme, -1));
}
int main() {
// freopen("regions.gir", "r", stdin);
// freopen("regions.cik", "w", stdout);
scanf("%d %d %d",&n ,&m ,&q);
scanf("%d",a + 1);
say[a[1]]++;
for(int i = 2; i <= n; i++){
int x;
scanf("%d %d",&x, a + i);
say[a[i]]++;
g[x].pb(i);
}
for(int i = 1; i <= m; i++)
if(say[i] >= kok){
mi[i] = ++k;
ne[k] = i;
}
memset(say, 0, sizeof say);
bul(1);
memset(say, 0, sizeof say);
bul2(1);
// cout << "AMK" << k << endl;
// for(int i = 1; i <= k; i++) {
// // cout << "AMK" << endl;
// for(int j = 1; j <= m; j++)
// if(j != ne[i]){
// // bul2(1, ne[i], 0, j, i);
// printf("ust[%d][%d] = %d\n", ne[i], j, ust[i][j]);
// printf("alt[%d][%d] = %d\n", ne[i], j, alt[i][j]);
// }
// }
dfs(1);
for(int i = 1; i <= m; i++) // O(N)
sort(gez[i].begin(), gez[i].end());
while(q--){
int x, y;
scanf("%d %d",&x, &y);
if(mi[x]){
printf("%d\n", alt[mi[x]][y]);
continue;
}
if(mi[y]){
printf("%d\n", ust[mi[y]][x]);
continue;
}
vector < iii > z; // O(kok)
int sz1 = gez[x].size(), i = 0;
int sz2 = gez[y].size(), j = 0;
// cout << x << " " << sz1 << " , " << y << " " << sz2 << endl;
while(i < sz1 and j < sz2){
if(gez[x][i].st < gez[y][j].st){
z.pb(mp(gez[x][i].st , mp(gez[x][i].nd, x)));
i++;
} else{
z.pb(mp(gez[y][j].st , mp(gez[y][j].nd, y)));
j++;
}
}
while(i < sz1){
z.pb(mp(gez[x][i].st , mp(gez[x][i].nd, x)));
i++;
}
while(j < sz2){
z.pb(mp(gez[y][j].st , mp(gez[y][j].nd, y)));
j++;
}
int crp = 0, ans = 0;
for(i = 0; i < z.size(); i++){
if(z[i].nd.nd == x)
crp += z[i].nd.st;
else
ans += crp;
}
printf("%d\n", ans/2);
}
return 0;
}
Compilation message
regions.cpp: In function 'void bul(int)':
regions.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
regions.cpp: In function 'void bul2(int)':
regions.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
regions.cpp: In function 'void dfs(int)':
regions.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:123:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < z.size(); i++){
~~^~~~~~~~~~
regions.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&n ,&m ,&q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",a + 1);
~~~~~^~~~~~~~~~~~
regions.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x, a + i);
~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
11 ms |
10488 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
10 ms |
10492 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
10 ms |
10488 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
8 ms |
10488 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
9 ms |
10616 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
10 ms |
10492 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
9 ms |
10488 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
9 ms |
10616 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
10 ms |
11000 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
14 ms |
11000 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
14 ms |
11304 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
16 ms |
11896 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
18 ms |
11640 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
23 ms |
12280 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
22 ms |
14840 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
41 ms |
15348 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
50 ms |
14372 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
51 ms |
17140 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
23 ms |
12152 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
24 ms |
13768 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
90 ms |
14584 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
49 ms |
14456 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
59 ms |
19704 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
111 ms |
20344 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
80 ms |
24440 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
122 ms |
19852 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
546 ms |
21488 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
472 ms |
21876 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
958 ms |
24820 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
750 ms |
25836 KB |
Time limit exceeded (wall clock) |
| 16 |
Execution timed out |
585 ms |
30704 KB |
Time limit exceeded (wall clock) |
| 17 |
Execution timed out |
905 ms |
33728 KB |
Time limit exceeded (wall clock) |
