# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1026970 | 2024-07-18T15:48:32 Z | Summers | Regions (IOI09_regions) | C++14 | 3369 ms | 120808 KB |
#include<bits/stdc++.h> #include<vector> using namespace std; vector<long long> v[1000000],d[1000000], ans[1000000],c[1000000]; long long t=1, p[1000000], tin[1000000], tout[1000000]; void dfs(long long vr) { tin[vr]=t++; d[p[vr]].push_back(tin[vr]); for (int i=0;i<v[vr].size();i++) { dfs(v[vr][i]); } tout[vr]=t; } void dfs1(long long br, long long vr,long long val) { if(val==p[vr])br++; else ans[val][p[vr]]+=br; for(int i=0;i<v[vr].size();i++) { dfs1(br, v[vr][i], val); } } int main() { long long i,j,r,q,n,h,s,a,b; cin>>n>>r>>q; cin>>h; p[1]=h; c[h].push_back(1); for(i=2;i<=n;i++) { cin>>s>>h; p[i]=h; v[s].push_back(i); c[h].push_back(i); } dfs(1); for(i=1;i<=r;i++) { if(d[i].size()>=1000) { ans[i].resize(r+1); dfs1(0,1,i); } } while(q--) { cin>>a>>b; if(d[a].size()>=1000) { cout<<ans[a][b]<<endl; cout.flush(); } else { long long an=0; for (long long i=0;i<c[a].size();i++) { auto it1 = upper_bound(d[b].begin(), d[b].end(), tout[c[a][i]]-1); it1--; auto it2 =lower_bound(d[b].begin(), d[b].end(), tin[c[a][i]]); an+=it1-it2+1; } cout<<an<<endl; cout.flush(); } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 94296 KB | Output is correct |
2 | Correct | 20 ms | 94296 KB | Output is correct |
3 | Correct | 20 ms | 94296 KB | Output is correct |
4 | Correct | 21 ms | 94296 KB | Output is correct |
5 | Correct | 23 ms | 94248 KB | Output is correct |
6 | Correct | 27 ms | 94296 KB | Output is correct |
7 | Correct | 33 ms | 94296 KB | Output is correct |
8 | Correct | 36 ms | 94388 KB | Output is correct |
9 | Correct | 37 ms | 94808 KB | Output is correct |
10 | Correct | 67 ms | 94956 KB | Output is correct |
11 | Correct | 94 ms | 95576 KB | Output is correct |
12 | Correct | 113 ms | 96188 KB | Output is correct |
13 | Correct | 158 ms | 95948 KB | Output is correct |
14 | Correct | 204 ms | 96600 KB | Output is correct |
15 | Correct | 212 ms | 99416 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1571 ms | 100676 KB | Output is correct |
2 | Correct | 1766 ms | 99776 KB | Output is correct |
3 | Correct | 2123 ms | 102776 KB | Output is correct |
4 | Correct | 215 ms | 96592 KB | Output is correct |
5 | Correct | 286 ms | 98384 KB | Output is correct |
6 | Correct | 1020 ms | 98900 KB | Output is correct |
7 | Correct | 1301 ms | 100456 KB | Output is correct |
8 | Correct | 957 ms | 106064 KB | Output is correct |
9 | Correct | 1736 ms | 108152 KB | Output is correct |
10 | Correct | 3329 ms | 112668 KB | Output is correct |
11 | Correct | 3369 ms | 108880 KB | Output is correct |
12 | Correct | 1201 ms | 110008 KB | Output is correct |
13 | Correct | 1562 ms | 110292 KB | Output is correct |
14 | Correct | 2086 ms | 112348 KB | Output is correct |
15 | Correct | 2568 ms | 114464 KB | Output is correct |
16 | Correct | 2501 ms | 119528 KB | Output is correct |
17 | Correct | 2368 ms | 120808 KB | Output is correct |