Submission #67533

#	Time	Username	Problem	Language	Result	Execution time	Memory
67533		imeimi2000	Regions (IOI09_regions)	C++17	100 / 100	3411 ms	105012 KiB

regions

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int t = 400;
const int tct = 500;
int n, r, q;
int h[200001];
int s[200001];
vector<int> child[200001];
vector<int> group[25001];
int st[200001];
int ed[200001];
int cnt[25001];
int big[25001];
int rc[25001][t];
int dc[25001][t];
int tp1[t];
int tp2[t];

void dfs(int x) {
    static int ord = 0;
    st[x] = ++ord;
    group[h[x]].push_back(ord);
    if (big[h[x]] != -1) ++tp1[big[h[x]]], ++tp2[big[h[x]]];
    for (int i = 0; i < t; ++i) {
        dc[h[x]][i] -= tp2[i];
    }
    for (int i : child[x]) {
        dfs(i);
    }
    if (big[h[x]] != -1) --tp1[big[h[x]]];
    for (int i = 0; i < t; ++i) {
        rc[h[x]][i] += tp1[i];
        dc[h[x]][i] += tp2[i];
    }
    ed[x] = ord;
    group[h[x]].push_back(-ord);
}

int main() {
    scanf("%d%d%d%d", &n, &r, &q, h + 1);
    for (int i = 2; i <= n; ++i) {
        scanf("%d%d", s + i, h + i);
        child[s[i]].push_back(i);
        ++cnt[h[i]];
    }
    for (int i = 1, j = 0; i <= r; ++i) {
        if (cnt[i] > tct) big[i] = j++;
        else big[i] = -1;
    }
    dfs(1);
    for (int i = 0; i < q; ++i) {
        int r1, r2, ans = 0;
        scanf("%d%d", &r1, &r2);
        
        if (big[r2] != -1) {
            ans = dc[r1][big[r2]];
        }
        else if (big[r1] != -1) {
            ans = rc[r2][big[r1]];
        }
        else {
            int cnt = 0, k = 0, p;
            for (int j : group[r1]) {
                if (j > 0) p = j;
                else p = 1 - j;
                while (k < group[r2].size()) {
                    int x = group[r2][k];
                    if (x > 0) {
                        if (x < p) ans += cnt;
                        else break;
                    }
                    ++k;
                }
                if (j > 0) ++cnt;
                else --cnt;
            }
        }
        
        printf("%d\n", ans);
        fflush(stdout);
    }
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:84:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while (k < group[r2].size()) {
                        ~~^~~~~~~~~~~~~~~~~~
regions.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &r, &q, h + 1);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", s + i, h + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &r1, &r2);
         ~~~~~^~~~~~~~~~~~~~~~~~

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