Submission #519886

#	Time	Username	Problem	Language	Result	Execution time	Memory
519886		LptN21	Regions (IOI09_regions)	C++14	0 / 100	106 ms	38816 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define PI acos(-1.0)
#define eps 1e-9
#define FF first
#define SS second
// VECTOR (6)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() );
// BIT (6)
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, int> ii;

/* */
template<class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template<class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
/* */

/* CODE BELOW */
const int N = 2e5 + 7, M = 1e9 + 7;
const int oo = 1e9 + 7;
const int MOD = 1e9 + 7;

int n, r, q;

const int BL = 106;


class FenwickTree{
private: int n;
    vector<int> bit;
public:
    FenwickTree(int _n = 0):n(_n) {
        bit.assign(_n + 1, 0);
    }

    void update(int p, int v) {
        for(;p<=n;p+=p&-p) {
            bit[p]+= v;
        }
    }

    int query(int l, int r) {
        int ans = 0;
        for(--l;l>0;l-=l&-l) ans-= bit[l];
        for(;r>0;r-=r&-r) ans+= bit[r];
        return ans;
    }
};

FenwickTree bit(N);

int in[N], out[N], cnt = 0;
vector<int> adj[N];
vector<int> region[N];

int cover[N];
int ans[N], type[N];
vector<ii> R1Group[N];
vector<ii> R2Group[N];
vector<ii> naiveQuery;

void dfs(int u) {
    region[type[u]].pb(u);
    in[u] = ++cnt;
    for(int v:adj[u]) dfs(v);
    out[u] = cnt;
}

int solve1(int u, int v) { // r1, r2 small
    int ans = 0;
    for(int x:region[v]) {
        bit.update(in[x], 1);
    }
    for(int x:region[u]) {
        ans+= bit.query(in[x], out[x]);
    }
    for(int x:region[v]) {
        bit.update(in[x], -1);
    }
    return ans;
}

void solve2() { // r1 big, r2 big/small
    for(int t=1;t<=r;t++) {
        if(sz(region[t])>M) {
            sort(all(R1Group[t]));
            for(int v:region[t]) {
                cover[in[v]]++;
                cover[out[v]+1]--;
            }
            for(int i=1;i<=n;i++) {
                cover[i]+= cover[i-1];
            }

            // process query
            int u, idx;
            for(int i=0;i<sz(R1Group[t]);i++) {
                tie(u, idx) = R1Group[t][i];
                if(i && R1Group[t][i-1].FF == u) {
                    ans[idx] = ans[R1Group[t][i-1].SS];
                    continue;
                }
                for(int v:region[u]) {
                    ans[idx]+= cover[in[v]];
                }
            }

            for(int i=1;i<=n;i++) cover[i] = 0;
        }
    }
}

void solve3() { // r1 big/small, r2 big
    for(int t=1;t<=r;t++) {
        if(sz(region[t])>M) {
            sort(all(R2Group[t]));
            for(int v:region[t]) {
                cover[in[v]]++;
            }
            for(int i=1;i<=n;i++) {
                cover[i]+= cover[i-1];
            }

            // process query
            int u, idx;
            for(int i=0;i<sz(R2Group[t]);i++) {
                tie(u, idx) = R2Group[t][i];
                if(i && R2Group[t][i-1].FF == u) {
                    ans[idx] = ans[R2Group[t][i-1].SS];
                    continue;
                }
                for(int v:region[u]) {
                    ans[idx]+= cover[out[v]] - cover[in[v]-1];
                }
            }

            for(int i=1;i<=n;i++) cover[i] = 0;
        }
    }
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d%d%d", &n, &r, &q);
    int u, v; scanf("%d", &type[1]);
    for(int i=2;i<=n;i++) {
        scanf("%d%d", &u, &type[i]);
        adj[u].pb(i);
    }
    dfs(1);

    for(int i=1;i<=q;i++) {
        scanf("%d%d", &u, &v);
        if(sz(region[u])<=M&&
           sz(region[v])<=M) {
            ans[i] = solve1(u, v);
        }
        if(sz(region[u])>M) {
            R1Group[u].pb(ii(v, i));
        } else if(sz(region[v])>M) {
            R2Group[v].pb(ii(u, i));
        }
    }
    solve2(), solve3();

    for(int i=1;i<=q;i++) {
        printf("%d\n", ans[i]);
    }

    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |     scanf("%d%d%d", &n, &r, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:170:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     int u, v; scanf("%d", &type[1]);
      |               ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         scanf("%d%d", &u, &type[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

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