답안 #852562

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852562 2023-09-22T05:38:46 Z abcvuitunggio Regions (IOI09_regions) C++17
25 / 100
285 ms 131072 KB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=416;
int n,R,q,r1,r2,cnt[200001][25000/sz+1],c[25001][25000/sz+1],c2[25001][25000/sz+1],r[200001],p[200001],tin[200001],tout[200001],t,C[25001],pos[25001];
vector <int> ke[200001],ve[25001],V;
void dfs(int u){
    tin[u]=++t;
    ve[r[u]].push_back(t);
    if (C[r[u]]>sz)
        cnt[u][pos[r[u]]]++;
    for (int v:ke[u]){
        for (int i=1;i<=sz;i++)
            cnt[v][i]+=cnt[u][i];
        dfs(v);
    }
    for (int i=1;i<=sz;i++)
        c[r[u]][i]+=cnt[u][i];
    tout[u]=++t;
    ve[r[u]].push_back(-t);
}
void dfs2(int u){
    if (C[r[u]]>sz)
        cnt[u][pos[r[u]]]++;
    for (int v:ke[u]){
        dfs2(v);
        for (int i=1;i<=sz;i++)
            cnt[u][i]+=cnt[v][i];
    }
    for (int i=1;i<=sz;i++)
        c2[r[u]][i]+=cnt[u][i];
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> R >> q;
    for (int i=1;i<=n;i++){
        if (i>1){
            cin >> p[i];
            ke[p[i]].push_back(i);
        }
        cin >> r[i];
        C[r[i]]++;
    }
    for (int i=1;i<=R;i++)
        V.push_back(i);
    sort(V.begin(),V.end(),[](int i, int j){return C[i]>C[j];});
    for (int i=0;i<V.size();i++)
        pos[V[i]]=i+1;
    dfs(1);
    memset(cnt,0,sizeof(cnt));
    dfs2(1);
    while (q--){
        cin >> r1 >> r2;
        if (C[r1]>sz){
            cout << c[r2][pos[r1]] << endl;
            continue;
        }
        if (C[r2]>sz){
            cout << c2[r1][pos[r2]] << endl;
            continue;
        }
        int j=0,cnt=0,res=0;
        for (int i=0;i<ve[r2].size();i++){
            while (j<ve[r1].size()){
                if (abs(ve[r1][j])>abs(ve[r2][i]))
                    break;
                cnt+=(ve[r1][j]>0)-(ve[r1][j]<0);
                j++;
            }
            if (ve[r2][i]>0)
                res+=cnt;
        }
        cout << res << endl;
    }
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:47:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i=0;i<V.size();i++)
      |                  ~^~~~~~~~~
regions.cpp:63:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i=0;i<ve[r2].size();i++){
      |                      ~^~~~~~~~~~~~~~
regions.cpp:64:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~
regions.cpp: In function 'void dfs2(long long int)':
regions.cpp:31:20: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
   31 |         c2[r[u]][i]+=cnt[u][i];
      |         ~~~~~~~~~~~^~~~~~~~~~~
regions.cpp:30:19: note: within this loop
   30 |     for (int i=1;i<=sz;i++)
      |                  ~^~~~
regions.cpp:28:22: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
   28 |             cnt[u][i]+=cnt[v][i];
      |             ~~~~~~~~~^~~~~~~~~~~
regions.cpp:27:23: note: within this loop
   27 |         for (int i=1;i<=sz;i++)
      |                      ~^~~~
regions.cpp: In function 'void dfs(long long int)':
regions.cpp:18:19: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
   18 |         c[r[u]][i]+=cnt[u][i];
      |         ~~~~~~~~~~^~~~~~~~~~~
regions.cpp:17:19: note: within this loop
   17 |     for (int i=1;i<=sz;i++)
      |                  ~^~~~
regions.cpp:14:22: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
   14 |             cnt[v][i]+=cnt[u][i];
      |             ~~~~~~~~~^~~~~~~~~~~
regions.cpp:13:23: note: within this loop
   13 |         for (int i=1;i<=sz;i++)
      |                      ~^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 110424 KB Output is correct
2 Correct 13 ms 110428 KB Output is correct
3 Correct 15 ms 110424 KB Output is correct
4 Correct 16 ms 110424 KB Output is correct
5 Correct 16 ms 110424 KB Output is correct
6 Correct 22 ms 110424 KB Output is correct
7 Correct 26 ms 110424 KB Output is correct
8 Correct 31 ms 110424 KB Output is correct
9 Correct 41 ms 110936 KB Output is correct
10 Correct 65 ms 110936 KB Output is correct
11 Correct 95 ms 111696 KB Output is correct
12 Correct 103 ms 111972 KB Output is correct
13 Correct 128 ms 111660 KB Output is correct
14 Correct 163 ms 112248 KB Output is correct
15 Correct 218 ms 115964 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 119 ms 116300 KB Execution killed with signal 13
2 Runtime error 119 ms 114884 KB Execution killed with signal 13
3 Runtime error 141 ms 117840 KB Execution killed with signal 13
4 Correct 189 ms 116344 KB Output is correct
5 Correct 285 ms 118624 KB Output is correct
6 Runtime error 99 ms 122400 KB Execution killed with signal 13
7 Runtime error 124 ms 124764 KB Execution killed with signal 13
8 Runtime error 168 ms 130232 KB Execution killed with signal 13
9 Runtime error 180 ms 131072 KB Execution killed with signal 9
10 Runtime error 175 ms 131072 KB Execution killed with signal 9
11 Runtime error 221 ms 131072 KB Execution killed with signal 9
12 Runtime error 265 ms 131072 KB Execution killed with signal 9
13 Runtime error 206 ms 131072 KB Execution killed with signal 9
14 Runtime error 278 ms 131072 KB Execution killed with signal 9
15 Runtime error 80 ms 131072 KB Execution killed with signal 9
16 Runtime error 105 ms 131072 KB Execution killed with signal 9
17 Runtime error 103 ms 131072 KB Execution killed with signal 9