Submission #939906

#	Time	Username	Problem	Language	Result	Execution time	Memory
939906		idiotcomputer	Regions (IOI09_regions)	C++11	95 / 100	2477 ms	131072 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int 
#define sz size

const int mxN = 2e5;
const int mxR = 25*1e3;
int n,r;

vector<int> adj[mxN];
int reg[mxN];
vector<int> all[mxR];
int first[mxN];
int ssize[mxN];
vector<int> ord;

unordered_map<int,ll> cnts[mxR];
unordered_map<int,ll> rcnts[mxR];
int tarr[mxN+1];

void dfs(int node, int p){
    first[node] = ord.sz();
    all[reg[node]].pb(node);
    ord.pb(node);
    ssize[node] = 1;
    for (int next : adj[node]){
        if (next != p){
            dfs(next,node);
            ssize[node] += ssize[next];
        }
    }
}



int main()
{
   // ios_base::sync_with_stdio(false);
   // cin.tie(NULL);
    
    int q;
    cin >> n >> r >> q;
    int a,b;
    cin >> a;
    reg[0] = a-1;
    for (int i = 1; i < n; i++){
        cin >> b >> a;
        a -= 1;
        b -= 1;
        reg[i] = a;
        adj[i].pb(b);
        adj[b].pb(i);
    }
    
    dfs(0,-1);
    int gsize = sqrt(n);
    for (int i = 0; i < r; i++){
        if (all[i].sz() <= gsize){
            continue;
        }
     //   cnts[i].resize(n);
        memset(tarr,0,sizeof(tarr));
        for (int j =0; j < all[i].sz(); j++){
            tarr[first[all[i][j]]] += 1;
            tarr[first[all[i][j]] + ssize[all[i][j]]] -= 1;
        }
        for (int j = 0; j < n; j++){
            if (j > 0) tarr[j] += tarr[j-1];
            cnts[i][reg[ord[j]]] += tarr[j];
        }
     //   rcnts[i].resize(n);
        memset(tarr,0,sizeof(tarr));
        for (int j =0; j < all[i].sz(); j++){
            tarr[first[all[i][j]]] += 1;
        }
        for (int j = 1; j < n; j++){
            tarr[j] += tarr[j-1];
        }
        for (int j = 0; j < n; j++){
            rcnts[i][reg[ord[j]]] += tarr[j+ssize[ord[j]]-1] - tarr[j];
        }
    }
    /*cout << gsize<< " gsize\n";
    for (int i =0; i < r; i++){
        cout << all[i].sz() << ":\n";
        for (int j = 0; j < all[i].sz(); j++) cout << all[i][j] << " ";
        cout << '\n';
        if (all[i].sz() <= gsize){
            continue;
        }
        for (int j =0; j < n; j++){
            cout << cnts[i][j] << " ";
        }
        cout << '\n';
        for (int j = 0; j < n; j++) cout << rcnts[i][j] << " ";
        cout << '\n';
    }
    */
    int c,idx;
    stack<int> p;
    ll res;
  /*  for (int i =0; i <r; i++){
        cout << i << ": ";
        for (int j : all[i]){
            cout << first[j] << "-" << ssize[j] << " ";
        }
        cout << '\n';
    }*/
    for (int i =0; i < q; i++){
        cin >> a >> b;
        a -= 1;
        b -= 1;
        if (all[a].sz() > gsize){
            cout << cnts[a][b] << '\n';
            continue;
        }
        if (all[b].sz() > gsize){
            cout << rcnts[b][a] << "\n";
            continue;
        }
        c = 0;
        idx = 0;
        res = 0;
       // cout << a << "," << b << ": ";
        for (int j = 0; j < all[b].sz(); j++){
          //  cout << p.sz() << " " << idx << " " << all[a].sz() << '\n';
            while (p.sz() > 0 && p.top() <= first[all[b][j]]){
                p.pop();
           //     cout << "Rm\n";
                c -= 1;
            }
         //   cout << ";\n";
            while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
                c += 1;
            //    cout << all[a][idx] << '\n';
                p.push(first[all[a][idx]] + ssize[all[a][idx]]);
                idx++;
                while (p.sz() > 0 && p.top() <= first[all[b][j]]){
                    p.pop();
                    c -= 1;
                }
            }
         //   cout << p.sz() << "l\n";
            
       //     cout << c << ' ' << p.top() << '\n';
    //   cout << c << '\n';
            res += c;
        }
        cout << res << '\n';
        while (p.sz() > 0){
            p.pop();
        }
    }
    
    
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:59:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         if (all[i].sz() <= gsize){
      |             ~~~~~~~~~~~~^~~~~~~~
regions.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int j =0; j < all[i].sz(); j++){
      |                        ~~^~~~~~~~~~~~~
regions.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int j =0; j < all[i].sz(); j++){
      |                        ~~^~~~~~~~~~~~~
regions.cpp:114:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |         if (all[a].sz() > gsize){
      |             ~~~~~~~~~~~~^~~~~~~
regions.cpp:118:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |         if (all[b].sz() > gsize){
      |             ~~~~~~~~~~~~^~~~~~~
regions.cpp:126:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for (int j = 0; j < all[b].sz(); j++){
      |                         ~~^~~~~~~~~~~~~
regions.cpp:134:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
      |                    ~~~~^~~~~~~~~~~~~

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