Submission #978918

#	Time	Username	Problem	Language	Result	Execution time	Memory
978918		AlphaMale06	Regions (IOI09_regions)	C++17	0 / 100	53 ms	24704 KiB

regions

#include <bits/stdc++.h>

using namespace std;

struct query{
    int a, b, ind, ans;
};

const int N = 2e5+3;

vector<int> g[N];
int a[N], tin[N], tout[N], cnt[N];
int f[2*N];
int timer=1;

void dfs(int v, int p){
    tin[v]=timer++;
    for(int to : g[v])dfs(to, v);
    tout[v]=timer++;
}

bool cmp(query A, query B){
    return A.a < B.a;
}

bool cmp2(query A, query B){
    return A.ind<B.ind;
}

void Update(int ind, int val){
    for(int i=ind; i<2*N; i+=i&-i)f[i]+=val;
}

int Get(int ind){
    int ret=0;
    for(int i=ind; i>0; i-=i&-i)ret+=f[i];
    return ret;
}

int Get(int l, int r){
    return Get(r)-Get(l-1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, r, q;
    cin >> n >> r >> q;
    cin >> a[1];
    cnt[a[1]]++;
    for(int i=2; i<=n; i++){
        int x;
        cin >> x >> a[i];
        cnt[a[i]]++;
        g[x].push_back(i);
    }
    dfs(1, 1);
    vector<query> ups;
    vector<query> downs;
    for(int i=0; i<q; i++){
        int u, v;
        cin >> u >> v;
        if(cnt[u]>cnt[v])ups.push_back({u, v, i, 0});
        else downs.push_back({v, u, i, 0});
    }
    sort(downs.begin(), downs.end(), cmp);
    sort(ups.begin(), ups.end(), cmp);
    vector<int> pos[r+1];
    for(int i=1; i<=n; i++){
        pos[a[i]].push_back(i);
    }
    if(downs.size()){
        for(int e : pos[downs[0].a])Update(tin[e], 1);
        for(int e : pos[downs[0].b])downs[0].ans+=Get(tin[e], tout[e]);
        for(int i=1; i<downs.size(); i++){
            if(downs[i].a!=downs[i-1].a){
                for(int e : pos[downs[i-1].a])Update(tin[e], -1);
                for(int e : pos[downs[i].a])Update(tin[e], 1);
            }
            for(int e : pos[downs[i].b])downs[i].ans+=Get(tin[e], tout[e]);
        }
    }
    for(int i=0; i<2*N; i++)f[i]=0;
    if(ups.size()){
        for(int e : pos[ups[0].a]){
            Update(tin[e], 1);
            Update(tout[e], -1);
        }
        for(int e : pos[ups[0].b])ups[0].ans+=Get(0, tin[e]);
        for(int i=1; i<ups.size(); i++){
            if(ups[i].a!=ups[i-1].a){
                for(int e : pos[ups[i-1].a]){
                    Update(tin[e], -1);
                    Update(tout[e], 1);
                }
                for(int e : pos[ups[i].a]){
                    Update(tin[e], 1);
                    Update(tout[e], -1);
                }
            }
            for(int e : pos[ups[i].b])ups[i].ans+=Get(0, tin[e]);
        }
    }
    vector<query> svi;
    for(auto & e : downs)svi.push_back(e);
    for(auto & e : ups)svi.push_back(e);
    sort(svi.begin(), svi.end(), cmp2);
    for(auto & e : svi)cout << e.ans << '\n';
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=1; i<downs.size(); i++){
      |                      ~^~~~~~~~~~~~~
regions.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int i=1; i<ups.size(); i++){
      |                      ~^~~~~~~~~~~

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