oj.uz

답안 #687081

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
687081 2023-01-26T05:58:21 Z boyliguanhan Regions (IOI09_regions) C++17
85 / 100
 8000 ms 71168 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define l long long
using namespace std;
vector<l> adj[200001], lg;
vector<pair<l,l>> arr[25001];
l region[200001], t, ans1[30][25001], ans2[25001][30], in[200001], out[200001], li[200001], sz[25001];
void merge(map<l, l> &a, map<l, l> b){
    if(a.size()<b.size())
        swap(a, b);
    for(auto i: b)
        a[i.first]+=i.second;
}
map<l,l> dfs(l n){
    map<l,l> cur;
    cur[region[n]]=1;
    in[n]=t++;
    arr[region[n]].push_back({in[n],1});
    for(auto i: adj[n]){
        merge(cur, dfs(i));
    }
    out[n]=t++;
    arr[region[n]].push_back({out[n],0});
    if(li[region[n]])
        for(auto i: cur)
            ans1[li[region[n]]][i.first]+=i.second;
    else
        for(auto i: lg)
            ans2[region[n]][li[i]]+=cur[i];
    return cur;
}
l query_s(int r1, int r2){
    l sum=0, o=0, a=0, b=0;
    vector<int> v;
    while(a<arr[r1].size()||b<arr[r2].size()){
        if(a<arr[r1].size()&&b<arr[r2].size()){
            if(arr[r1][a]<arr[r2][b])
                v.push_back(arr[r1][a].second*2-1), a++;
            else
                v.push_back(0), b++;
        } else if(a<arr[r1].size())
            v.push_back(arr[r1][a].second*2-1), a++;
        else
            v.push_back(0), b++;
    }
    for(auto i: v)
        if(i)
            o+=i;
        else
            sum+=o;
    return sum/2;
}
int main(){
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    l n, r, q, lr=0;
    cin >> n >> r >> q;
    cin >> region[1];
    for(l i = 2; i <= n; i++){
        l p;
        cin >> p >> region[i];
        sz[region[i]]++;
        adj[p].push_back(i);
    }
    for(int i = 1; i <= r; i++)
        if(sz[i]>5000)
            lg.push_back(i), li[i]=++lr;
    dfs(1);
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        if(li[r1])
            cout << ans1[li[r1]][r2] << endl;
        else if(li[r2])
            cout << ans2[r1][li[r2]] << endl;
        else
            cout << query_s(r1, r2) << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'long long int query_s(int, int)':
regions.cpp:35:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:35:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:36:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:36:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         } else if(a<arr[r1].size())
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 6 ms 5584 KB Output is correct
4 Correct 9 ms 5584 KB Output is correct
5 Correct 11 ms 5612 KB Output is correct
6 Correct 23 ms 5840 KB Output is correct
7 Correct 30 ms 5840 KB Output is correct
8 Correct 33 ms 5840 KB Output is correct
9 Correct 59 ms 7132 KB Output is correct
10 Correct 51 ms 6736 KB Output is correct
11 Correct 116 ms 7376 KB Output is correct
12 Correct 128 ms 8716 KB Output is correct
13 Correct 165 ms 8132 KB Output is correct
14 Correct 237 ms 9052 KB Output is correct
15 Correct 328 ms 17488 KB Output is correct

Subtask #2
70.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1046 ms 16004 KB Output is correct
2 Correct 1119 ms 13252 KB Output is correct
3 Correct 1918 ms 20872 KB Output is correct
4 Correct 227 ms 9508 KB Output is correct
5 Correct 362 ms 14536 KB Output is correct
6 Correct 875 ms 12420 KB Output is correct
7 Correct 1250 ms 14152 KB Output is correct
8 Correct 948 ms 30412 KB Output is correct
9 Correct 1727 ms 27004 KB Output is correct
10 Correct 3130 ms 42528 KB Output is correct
11 Correct 2924 ms 26672 KB Output is correct
12 Correct 1238 ms 30712 KB Output is correct
13 Correct 2052 ms 32688 KB Output is correct
14 Correct 2471 ms 33804 KB Output is correct
15 Execution timed out 8058 ms 47416 KB Time limit exceeded
16 Execution timed out 8090 ms 71168 KB Time limit exceeded
17 Execution timed out 8086 ms 66484 KB Time limit exceeded