| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94289 |
2019-01-17T10:38:50 Z |
ekrem |
Regions (IOI09_regions) |
C++ |
|
8000 ms |
38172 KB |
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 400005
#define M 25005
#define kok 4000
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 |
14 ms |
19064 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
17 ms |
19064 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
16 ms |
19064 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
17 ms |
19192 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
16 ms |
19064 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
16 ms |
19192 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
14 ms |
19192 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
15 ms |
19192 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
16 ms |
19704 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
20 ms |
19576 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
19 ms |
19960 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
21 ms |
20472 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
25 ms |
20216 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
31 ms |
20856 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
31 ms |
23544 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2162 ms |
24264 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
2670 ms |
23080 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
1534 ms |
26484 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
28 ms |
20856 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
32 ms |
22476 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
34 ms |
22008 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
44 ms |
23160 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
51 ms |
28024 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
83 ms |
29032 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
98 ms |
33144 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
116 ms |
28548 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
8074 ms |
26016 KB |
Time limit exceeded |
| 13 |
Execution timed out |
8077 ms |
26584 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8085 ms |
25720 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8084 ms |
30604 KB |
Time limit exceeded |
| 16 |
Execution timed out |
8077 ms |
38172 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8066 ms |
36732 KB |
Time limit exceeded |
