Submission #1228680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228680		minhpk	Regions (IOI09_regions)	C++20	0 / 100	7640 ms	64208 KiB

regions

#include <bits/stdc++.h>

using namespace std;
int a,b,c;
vector <int> z[1000005];
int t[1000005];
int sl[1000005];
int block;
int check[1000005];
int mark[1000005];
int cur=0;
int cnt[1000005];
int sta[1000005];
int fin[1000005];
int rev[1000005];
int child[1000005];
int tour;
int big[1000005];

int pre[501][501];
int res[1000005];
int cnt1[450][25005];
int cnt2[450][25005];

void predfs(int i,int parent){
    tour++;
    sta[i]=tour;
    rev[tour]=i;
    child[i]=1;
    big[i]=-1;

    for (auto p:z[i]){
         if (p==parent){
            continue;
         }

         predfs(p,i);
         child[i]+=child[p];
         if (big[i]==-1 || child[big[i]]<child[p]){
             big[i]=p;
         }
    }

    fin[i]=tour;
}

void dfs(int i,int parent,bool keep){
    for (auto p:z[i]){
         if (p==parent || p==big[i]){
             continue;
         }
         dfs(p,i,0);
    }
    if (big[i]!=-1){
         dfs(big[i],i,1);
    }

    for (auto p:z[i]){
         if (p==parent || p==big[i]){
            continue;
         }
         for (int j=sta[p];j<=fin[p];j++){
              int x=rev[j];
              if (mark[t[x]]){
                  cnt[mark[t[x]]]++;
              }
         }
    }

    if (mark[t[i]]){
        int x=mark[t[i]];
        for (int j=1;j<=cur;j++){
             if (j!=x){
                 pre[x][j]+=cnt[j];
             }
        }
        cnt[x]++;
    }

    if (!keep){
        for (int j=sta[i];j<=fin[i];j++){
             int x=rev[j];
             if (mark[t[x]]){
                  cnt[mark[t[x]]]--;
             }
        }
    }
}

vector <int> pos[25001];
struct BIT{
        int bit[300005];
        vector <int> used;
        void add(int i,int val){

             while (i<=a){
                 if (bit[i]==0){
                     used.push_back(i);
                 }
                 bit[i]+=val;
                 i+=i&-i;
             }
        }
        int query(int i){

            int res=0;
            while (i>0){
                 res+=bit[i];
                 i-=i&-i;
            }
            return res;
        }
        void reset(){
            for (auto p:used){
                 bit[p]=0;
            }
            used.clear();
        }
};
BIT f,f1,f2;
bool cmp(pair<int,int> a,pair<int,int> b){
    return sta[a.first]>sta[b.first];
}
int cal(int x,int y){
    vector <pair<int,int>> v;
    f2.reset();
    int res=0;
    for (auto p:pos[x]){
         v.push_back({p,1});
    }
    for (auto p:pos[y]){
         v.push_back({p,2});
    }
    sort(v.begin(),v.end(),cmp);
    for (auto [p1,p2] :v){
         if (p2==1){
             f2.add(fin[p1],1);
         }else{
             res+=f2.query(a)-f2.query(fin[p1]-1);
         }
    }
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> c;
    cin >> t[1];
    block=sqrt(a);
   // block=0;
    sl[t[1]]++;
    pos[t[1]].push_back(1);
    for (int i=2;i<=a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(i);
         t[i]=y;
         pos[t[i]].push_back(i);
         sl[y]++;
    }
    for (int i=1;i<=b;i++){
         if (sl[i]>block){
             cur++;
             mark[i]=cur;
             check[i]=1;
         }
    }
    predfs(1,0);
    dfs(1,0,1);

    // heavy child
    for (int i=1;i<=b;i++){
       if (mark[i]){
         for (auto p:pos[i]){
              f.add(sta[p],1);
//              if (i==3){
//                  cout << sta[p] << "\n";
//              }
         }
         for (int j=1;j<=b;j++){
              if (!mark[j]){
                  for (auto p:pos[j]){
//                     if (i==3 && j==1){
//                         cout << p << " " << fin[p] << " " << sta[p] << " " << f.query(fin[p])-f.query(sta[p]-1) << "\n";
//                     }
                       cnt1[mark[i]][j]+=f.query(fin[p])-f.query(sta[p]-1);
                  }
              }
         }
         f.reset();
       }
    }
  //  cout << pos[1][0] << " ";
    //heavy par
    for (int i=1;i<=b;i++){
        if (mark[i]){
            for (auto p:pos[i]){
              f1.add(sta[p],1);
              f1.add(fin[p]+1,-1);
            }
            for (int j=1;j<=b;j++){
              if (!mark[j]){
                  for (auto p:pos[j]){
                       cnt2[mark[i]][j]+=f1.query(sta[p]);
                  }
              }
            }
           f1.reset();
        }
    }

    while (c--){
         int x,y;
         cin >> x >> y;
         if (mark[x] && mark[y]){
             cout << pre[x][y] << "\n";
             cout << flush;
         }else if (mark[x] || mark[y]){
             if (mark[x]){
                 cout << cnt2[mark[x]][y]  << "\n";
                 cout << flush;
             }else{
                 cout << cnt1[mark[y]][x]  << "\n";
                 cout << flush;
             }
         }else{
             cout << cal(x,y) << "\n";
             cout << flush;
         }
    }
    return 0;
}

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