제출 #852562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852562		abcvuitunggio	Regions (IOI09_regions)	C++17	25 / 100	285 ms	131072 KiB

regions

#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;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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++)
      |                      ~^~~~

• Subtask 1: 15 / 15
• Subtask 2: 10 / 85