Submission #939908

#	Time	Username	Problem	Language	Result	Execution time	Memory
939908		idiotcomputer	Regions (IOI09_regions)	C++11	100 / 100	2346 ms	52700 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()
{

    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 = (double) 2 * sqrt(n);
    for (int i = 0; i < r; i++){
        if (all[i].sz() <= gsize){
            continue;
        }
        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];
        }
        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];
        }
    }
    
    
    int c,idx;
    stack<int> p;
    ll res;
 
    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;
        for (int j = 0; j < all[b].sz(); j++){
            while (p.sz() > 0 && p.top() <= first[all[b][j]]){
                p.pop();
                c -= 1;
            }
            while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
                c += 1;
                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;
                }
            }

            res += c;
        }
        cout << res << '\n';
        while (p.sz() > 0){
            p.pop();
        }
    }
    
    
    return 0;
}

Compilation message (stderr)

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

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