| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53551 |
2018-06-30T07:56:06 Z |
김세빈(#1419) |
Regions (IOI09_regions) |
C++11 |
|
8000 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
vector <int> V[202020], X[202020], K[25252];
vector <int> S, st;
int A[1010][25252], B[1010][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();
ret = 0;
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() > 200){
N[i] = s ++;
dfs(i, N[i], 1, 0);
}
}
for(;q--;){
scanf("%d%d", &a, &b);
if(K[a].size() > 200){
printf("%d\n",A[N[a]][b]);
}
else if(K[b].size() > 200){
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:93: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:93: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:94: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:94: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:98:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<S.size()-1;i++){
~^~~~~~~~~~~
regions.cpp:106: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:124: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:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", T+1);
~~~~~^~~~~~~~~~~
regions.cpp:130: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:153: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 |
Correct |
12 ms |
10360 KB |
Output is correct |
| 2 |
Correct |
14 ms |
10424 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10456 KB |
Output is correct |
| 4 |
Correct |
14 ms |
10588 KB |
Output is correct |
| 5 |
Correct |
23 ms |
10708 KB |
Output is correct |
| 6 |
Runtime error |
41 ms |
21156 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Incorrect |
61 ms |
21192 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
53 ms |
21396 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
94 ms |
22084 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
267 ms |
22576 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
716 ms |
23616 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
561 ms |
24624 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
997 ms |
24624 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
2895 ms |
25752 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
3038 ms |
30880 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3846 ms |
33540 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
1536 ms |
33540 KB |
Unexpected end of file - int32 expected |
| 3 |
Execution timed out |
8010 ms |
37312 KB |
Time limit exceeded |
| 4 |
Incorrect |
2468 ms |
37312 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
2282 ms |
37312 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
1056 ms |
37312 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
3686 ms |
37312 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
4388 ms |
49920 KB |
Unexpected end of file - int32 expected |
| 9 |
Execution timed out |
8045 ms |
56960 KB |
Time limit exceeded |
| 10 |
Execution timed out |
7874 ms |
122680 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
8109 ms |
129448 KB |
Time limit exceeded |
| 12 |
Execution timed out |
8074 ms |
129448 KB |
Time limit exceeded |
| 13 |
Execution timed out |
8007 ms |
129448 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8007 ms |
129448 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8087 ms |
129448 KB |
Time limit exceeded |
| 16 |
Execution timed out |
6521 ms |
131072 KB |
Time limit exceeded (wall clock) |
| 17 |
Execution timed out |
8068 ms |
131072 KB |
Time limit exceeded |
