| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53547 |
2018-06-30T07:45:57 Z |
김세빈(#1419) |
Regions (IOI09_regions) |
C++11 |
|
8000 ms |
74084 KB |
#include <bits/stdc++.h>
using namespace std;
vector <int> V[202020], X[202020], K[25252];
vector <int> S, st;
int A[505][25252], B[505][25252];
int dep[202020], P[202020][20];
int L[202020], R[202020], N[202020], T[202020];
int n, k, cnt, s;
bool comp_L(int ca, int cb) { return L[ca] < L[cb]; }
int dfs_order(int p)
{
int i;
L[p] = R[p] = cnt++;
for(i=0;i<V[p].size();i++){
P[V[p][i]][0]= p;
dep[V[p][i]] = dep[p] + 1;
R[p] = dfs_order(V[p][i]);
}
return R[p];
}
int dfs(int r, int x, int p, int d)
{
int i, ret;
if(T[p] == r){
ret = 1;
d ++;
}
else{
ret = 0;
A[x][T[p]] += d;
}
for(i=0;i<V[p].size();i++){
ret += dfs(r, x, V[p][i], d);
}
if(T[p] != r){
B[x][T[p]] += ret;
}
return ret;
}
void dfs_query(int &ans, int a, int b, int p, int d)
{
int i;
if(T[p] == a) d ++;
else if(T[p] == b) ans += d;
for(i=0;i<X[p].size();i++){
dfs_query(ans, a, b, X[p][i], d);
X[X[p][i]].clear();
}
}
int lca(int a, int b)
{
int i;
if(dep[a] < dep[b]) swap(a, b);
for(i=0;i<=18;i++){
if(dep[a] - dep[b] & (1<<i)) a = P[a][i];
}
if(a == b) return a;
for(i=18;i>=0;i--){
if(P[a][i] != P[b][i]) a = P[a][i], b = P[b][i];
}
return P[a][0];
}
int query(int a, int b)
{
int i,j,ret;
S.clear();
st.clear();
for(i=0,j=0; i<K[a].size() || j<K[b].size();){
if(i == K[a].size() || (j != K[b].size() && L[K[a][i]] > L[K[b][j]])) S.push_back(K[b][j++]);
else S.push_back(K[a][i++]);
}
for(i=0;i<S.size()-1;i++){
j = lca(S[i], S[i+1]);
if(j != S[i] && j != S[i+1]) S.push_back(j);
}
sort(S.begin(), S.end(), comp_L);
S.erase(unique(S.begin(), S.end()), S.end());
for(i=0;i<S.size();i++){
for(;!st.empty() && R[st.back()] < L[S[i]]; st.pop_back());
if(!st.empty()){
X[st.back()].push_back(S[i]);
}
st.push_back(S[i]);
}
dfs_query(ret, a, b, S[0], 0);
X[S[0]].clear();
return ret;
}
int main()
{
//freopen("input.txt","r",stdin);
int i,j,a,b,q;
scanf("%d%d%d", &n, &k, &q);
scanf("%d", T+1);
K[T[1]].push_back(1);
for(i=2;i<=n;i++){
scanf("%d%d", &a, T+i);
V[a].push_back(i);
K[T[i]].push_back(i);
}
dfs_order(1);
for(i=1;i<=18;i++){
for(j=1;j<=n;j++){
P[j][i] = P[P[j][i-1]][i-1];
}
}
for(i=1;i<=k;i++){
sort(K[i].begin(), K[i].end(), comp_L);
if(K[i].size() > 400){
N[i] = s ++;
dfs(i, N[i], 1, 0);
}
}
for(;q--;){
scanf("%d%d", &a, &b);
if(K[a].size() > 400){
printf("%d\n",A[N[a]][b]);
}
else if(K[b].size() > 400){
printf("%d\n",B[N[b]][a]);
}
else{
printf("%d\n",query(a, b));
}
fflush(stdout);
}
return 0;
}
Compilation message
regions.cpp: In function 'int dfs_order(int)':
regions.cpp:20:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<V[p].size();i++){
~^~~~~~~~~~~~
regions.cpp: In function 'int dfs(int, int, int, int)':
regions.cpp:42:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<V[p].size();i++){
~^~~~~~~~~~~~
regions.cpp: In function 'void dfs_query(int&, int, int, int, int)':
regions.cpp:60:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<X[p].size();i++){
~^~~~~~~~~~~~
regions.cpp: In function 'int lca(int, int)':
regions.cpp:73:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
if(dep[a] - dep[b] & (1<<i)) a = P[a][i];
~~~~~~~^~~~~~~~
regions.cpp: In function 'int query(int, int)':
regions.cpp:92:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0,j=0; i<K[a].size() || j<K[b].size();){
~^~~~~~~~~~~~
regions.cpp:92:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0,j=0; i<K[a].size() || j<K[b].size();){
~^~~~~~~~~~~~
regions.cpp:93:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == K[a].size() || (j != K[b].size() && L[K[a][i]] > L[K[b][j]])) S.push_back(K[b][j++]);
~~^~~~~~~~~~~~~~
regions.cpp:93:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == K[a].size() || (j != K[b].size() && L[K[a][i]] > L[K[b][j]])) S.push_back(K[b][j++]);
~~^~~~~~~~~~~~~~
regions.cpp:97:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<S.size()-1;i++){
~^~~~~~~~~~~
regions.cpp:105:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<S.size();i++){
~^~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &k, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", T+1);
~~~~~^~~~~~~~~~~
regions.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, T+i);
~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
10488 KB |
Output isn't correct |
| 2 |
Incorrect |
11 ms |
10552 KB |
Output isn't correct |
| 3 |
Incorrect |
13 ms |
10552 KB |
Output isn't correct |
| 4 |
Incorrect |
17 ms |
10552 KB |
Output isn't correct |
| 5 |
Incorrect |
21 ms |
10704 KB |
Output isn't correct |
| 6 |
Runtime error |
31 ms |
21308 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Incorrect |
60 ms |
21352 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
63 ms |
21352 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
110 ms |
22140 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
348 ms |
22588 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
789 ms |
23624 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
663 ms |
24728 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
1098 ms |
24728 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
2781 ms |
25700 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
2819 ms |
29572 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8051 ms |
33524 KB |
Time limit exceeded |
| 2 |
Execution timed out |
8023 ms |
33524 KB |
Time limit exceeded |
| 3 |
Execution timed out |
8022 ms |
37456 KB |
Time limit exceeded |
| 4 |
Incorrect |
2582 ms |
37456 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
1674 ms |
37456 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
822 ms |
37456 KB |
Unexpected end of file - int32 expected |
| 7 |
Execution timed out |
8042 ms |
37456 KB |
Time limit exceeded |
| 8 |
Incorrect |
3941 ms |
49904 KB |
Unexpected end of file - int32 expected |
| 9 |
Execution timed out |
8087 ms |
49904 KB |
Time limit exceeded |
| 10 |
Execution timed out |
8045 ms |
74084 KB |
Time limit exceeded |
| 11 |
Execution timed out |
8085 ms |
74084 KB |
Time limit exceeded |
| 12 |
Execution timed out |
8029 ms |
74084 KB |
Time limit exceeded |
| 13 |
Execution timed out |
8064 ms |
74084 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8034 ms |
74084 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8034 ms |
74084 KB |
Time limit exceeded |
| 16 |
Execution timed out |
8071 ms |
74084 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8018 ms |
74084 KB |
Time limit exceeded |
