oj.uz

답안 #686978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
686978 2023-01-26T04:43:43 Z boyliguanhan Regions (IOI09_regions) C++17
13 / 100
 238 ms 24520 KB 
#include<bits/stdc++.h>
#define l long long
using namespace std;
vector<l> adj[200001], lg;
vector<pair<l,l>> arr[25001];
l region[25001], t, ans1[501][25001], ans2[25001][501], in[25001], out[25001], 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[n])
        for(auto i: cur)
            ans1[li[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(){
    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]>500)
            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:34: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]
   34 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:34: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]
   34 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:35: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]
   35 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:35: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]
   35 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:40: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]
   40 |         } else if(a<arr[r1].size())
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
13.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5584 KB Output is correct
2 Correct 5 ms 5584 KB Output is correct
3 Correct 7 ms 5604 KB Output is correct
4 Correct 10 ms 5584 KB Output is correct
5 Correct 12 ms 5584 KB Output is correct
6 Correct 13 ms 5840 KB Output is correct
7 Correct 41 ms 5712 KB Output is correct
8 Correct 32 ms 5840 KB Output is correct
9 Correct 61 ms 7112 KB Output is correct
10 Correct 103 ms 6736 KB Output is correct
11 Correct 143 ms 7352 KB Output is correct
12 Correct 167 ms 8656 KB Output is correct
13 Correct 238 ms 8064 KB Output is correct
14 Runtime error 41 ms 13136 KB Execution killed with signal 11
15 Runtime error 35 ms 14004 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 63 ms 16004 KB Execution killed with signal 11
2 Runtime error 65 ms 14896 KB Execution killed with signal 11
3 Runtime error 77 ms 17132 KB Execution killed with signal 11
4 Runtime error 31 ms 13040 KB Execution killed with signal 11
5 Runtime error 36 ms 13872 KB Execution killed with signal 11
6 Runtime error 45 ms 14316 KB Execution killed with signal 11
7 Runtime error 61 ms 15400 KB Execution killed with signal 11
8 Runtime error 72 ms 17908 KB Execution killed with signal 11
9 Runtime error 115 ms 20636 KB Execution killed with signal 11
10 Runtime error 155 ms 22592 KB Execution killed with signal 11
11 Runtime error 183 ms 20132 KB Execution killed with signal 11
12 Runtime error 142 ms 23620 KB Execution killed with signal 11
13 Runtime error 159 ms 22660 KB Execution killed with signal 11
14 Runtime error 158 ms 22468 KB Execution killed with signal 11
15 Runtime error 170 ms 24520 KB Execution killed with signal 11
16 Runtime error 176 ms 24496 KB Execution killed with signal 11
17 Runtime error 177 ms 24392 KB Execution killed with signal 11