Submission #299387

#	Time	Username	Problem	Language	Result	Execution time	Memory
299387		mat_v	Regions (IOI09_regions)	C++14	45 / 100	4879 ms	128880 KiB

regions

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define maxn 200005

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int dlt = 500;
int t = 0;

int n,r,q;
vector<int> graf[maxn];
int cnt[maxn];
int cale[maxn], niz[maxn];
int slika[maxn];
int rev[maxn];
int atm[maxn];
int in[maxn], out[maxn];
int dole[25010][505];
int gore[25010][505];
vector<pii> all[25005];
vector<int> ins[25005];
int br;


void dfs(int x){
    in[x] = ++t;
    atm[niz[x]]++;
    if(rev[niz[x]]){
        ff(i,1,r){
            dole[i][rev[niz[x]]] += atm[i];
        }
        dole[niz[x]][rev[niz[x]]]--;
        gore[niz[x]][rev[niz[x]]]--;
    }
    ff(i,1,br){
        gore[niz[x]][i] += atm[rev[i]];
    }
    for(auto c:graf[x]){
        if(c == cale[x])continue;
        dfs(c);
    }
    atm[niz[x]]--;
    out[x] = t;
    if(!rev[niz[x]]){
        all[niz[x]].pb({in[x], -1});
        all[niz[x]].pb({out[x], 1});
        ins[niz[x]].pb(in[x]);
    }
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> r >> q;
    ff(i,1,n){
        if(i == 1){
            cin >> niz[i];
            continue;
        }
        cin >> cale[i] >> niz[i];
        graf[i].pb(cale[i]);
        graf[cale[i]].pb(i);
        cnt[niz[i]]++;
    }
    ff(i,1,r){
        if(cnt[i] >= dlt){
            slika[i] = ++br;
            rev[br] = i;
        }
    }
    dfs(1);
    ff(i,1,r){
        sort(all[i].begin(), all[i].end());
        sort(ins[i].begin(), ins[i].end());
    }
    while(q--){
        int r1,r2;
        cin >> r1 >> r2;
        if(rev[r1]){
            cout << dole[r2][rev[r1]] << endl;
            continue;
        }
        if(rev[r2]){
            cout << gore[r1][rev[r2]] << endl;
            continue;
        }
        int ans = 0;
        for(int i=0, j=0; i<all[r1].size();i++){
            while(j<ins[r2].size() && ins[r2][j] <= all[r1][i].xx)j++;
            ans += j*all[r1][i].yy;
        }
        cout << (ans) - (r1 == r2) * (ins[r1].size()) << endl;

    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:44:9: note: in expansion of macro 'ff'
   44 |         ff(i,1,r){
      |         ^~
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:50:5: note: in expansion of macro 'ff'
   50 |     ff(i,1,br){
      |     ^~
regions.cpp: In function 'int main()':
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:71:5: note: in expansion of macro 'ff'
   71 |     ff(i,1,n){
      |     ^~
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:81:5: note: in expansion of macro 'ff'
   81 |     ff(i,1,r){
      |     ^~
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:88:5: note: in expansion of macro 'ff'
   88 |     ff(i,1,r){
      |     ^~
regions.cpp:104:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int i=0, j=0; i<all[r1].size();i++){
      |                           ~^~~~~~~~~~~~~~~
regions.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             while(j<ins[r2].size() && ins[r2][j] <= all[r1][i].xx)j++;
      |                   ~^~~~~~~~~~~~~~~

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