| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53538 |
2018-06-30T07:35:05 Z |
김세빈(#1419) |
Regions (IOI09_regions) |
C++11 |
|
3002 ms |
10736 KB |
#include <bits/stdc++.h>
using namespace std;
vector <int> V[202020], X[202020], K[25252];
vector <int> S, st;
int A[2020][25252], B[2020][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() > 100){
N[i] = s ++;
dfs(i, N[i], 1, 0);
}
}
for(;q--;){
scanf("%d%d", &a, &b);
if(K[a].size() > 100){
printf("%d\n",A[N[a]][b]);
}
else if(K[b].size() > 100){
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:121:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.txt","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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 |
3002 ms |
10360 KB |
Output isn't correct |
| 2 |
Incorrect |
2945 ms |
10420 KB |
Output isn't correct |
| 3 |
Incorrect |
2835 ms |
10420 KB |
Output isn't correct |
| 4 |
Incorrect |
2838 ms |
10420 KB |
Output isn't correct |
| 5 |
Incorrect |
2839 ms |
10420 KB |
Output isn't correct |
| 6 |
Incorrect |
2892 ms |
10532 KB |
Output isn't correct |
| 7 |
Incorrect |
2685 ms |
10608 KB |
Output isn't correct |
| 8 |
Incorrect |
2735 ms |
10608 KB |
Output isn't correct |
| 9 |
Execution timed out |
19 ms |
10608 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
17 ms |
10608 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
17 ms |
10608 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
19 ms |
10608 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
19 ms |
10608 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
19 ms |
10608 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
23 ms |
10608 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
17 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
17 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
18 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
17 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
23 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
19 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
18 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
19 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
18 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
21 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
17 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
17 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
18 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
19 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 16 |
Execution timed out |
17 ms |
10736 KB |
Time limit exceeded (wall clock) |
| 17 |
Execution timed out |
17 ms |
10736 KB |
Time limit exceeded (wall clock) |
