| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94290 |
2019-01-17T10:52:15 Z |
ekrem |
Regions (IOI09_regions) |
C++ |
|
8000 ms |
28840 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 1000
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, int ne, int say, int dur, int kk){
if(a[node] == ne)
say++;
if(a[node] == dur)
ust[kk][ne] += say;
for(int i = 0; i < g[node].size(); i++)
bul(g[node][i], ne, say, dur, kk);
}
void bul2(int node, int ne, int say, int dur, int kk){
if(a[node] == ne)
say++;
if(a[node] == dur)
alt[kk][dur] += say;
for(int i = 0; i < g[node].size(); i++)
bul2(g[node][i], ne, say, dur, kk);
}
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;
}
for(int i = 1; i <= k; i++)
for(int j = 1; j <= m; j++)
if(j != ne[i]){
bul(1, j, 0, ne[i], 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++)
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;
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, int, int, int, int)':
regions.cpp:23: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, int, int, int, int)':
regions.cpp:32: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:38: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:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < z.size(); i++){
~~^~~~~~~~~~
regions.cpp:47: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:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",a + 1);
~~~~~^~~~~~~~~~~~
regions.cpp:53: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:80: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 |
8 ms |
9720 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
8 ms |
9644 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
8 ms |
9648 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
8 ms |
9720 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
8 ms |
9720 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
9 ms |
9848 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
8 ms |
9848 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
9 ms |
9848 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
10 ms |
10232 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
13 ms |
10356 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
14 ms |
10488 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
14 ms |
11128 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
17 ms |
10872 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
19 ms |
11512 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
22 ms |
13944 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2188 ms |
14960 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
6702 ms |
13732 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
7477 ms |
16968 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
21 ms |
11512 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
21 ms |
13116 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
32 ms |
12664 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
38 ms |
13688 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
49 ms |
18680 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
87 ms |
19704 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
79 ms |
23800 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
110 ms |
19172 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
8032 ms |
16504 KB |
Time limit exceeded |
| 13 |
Execution timed out |
8029 ms |
16940 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8048 ms |
16248 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8029 ms |
21192 KB |
Time limit exceeded |
| 16 |
Execution timed out |
8064 ms |
28840 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8066 ms |
27284 KB |
Time limit exceeded |
