Submission #1112124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112124		FucKanh	Regions (IOI09_regions)	C++14	0 / 100	2778 ms	131072 KiB

regions

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>

using namespace std;


const int maxn = 2e5 + 2;
const int maxr = 25001;
const int maxb = 450;

int tin[maxn], tout[maxn], pos[maxr];
int large[maxb][maxn],t;
bool control[maxb][maxn];
int compute[maxb][maxb];
vector<int> a[maxn], grp[maxr];
vector<int> pre;

void dfs(int u) {
    tin[u] = ++t;
    for (int v : a[u]) dfs(v);
    tout[u] = t;
}

bool compare(const int &a, const int &b) {
    return tin[a] < tin[b];
}

void solve() {
    int n,r,q; cin >> n >> r >> q;
    int block = sqrt(n) + 1;
    int gt; cin >> gt;
    grp[gt].push_back(1);
    for (int i = 2; i <= n; i++) {
        int x,y; cin >> x >> y;
        a[x].push_back(i);
        grp[y].push_back(i);
    }
    dfs(1);
    for (int i = 1; i <= r; i++) {
        sort(grp[i].begin(),grp[i].end(),compare);
        if (grp[i].size() >= block) {
            pre.push_back(i);
            pos[i] = pre.size()-1;
        }
    }
    for (int i = 0; i < pre.size(); i++) {
        for (int v : grp[pre[i]]) {
            large[i][tin[v]]=1;
            for (int j = tout[v]; j >= tin[v]; j--) {
                if (control[i][j]) break;
                control[i][j] = 1;
            }
        }
        for (int j = 1; j <= n; j++) large[i][j] += large[i][j-1];

        for (int j = 0; j < pre.size(); j++) {
            if (i != j) {
                for (int v : grp[pre[j]]) {
                    compute[i][j]+=control[i][tin[v]];
                }
            }
        }
    }

    for (int i = 1; i <= q; i++) {
        int x,y; cin >> x >> y;
        int ans = 0;
        if (grp[x].size() >= block && grp[y].size() >= block) {
            cout << compute[pos[x]][pos[y]] << endl;
        }
        else if (grp[x].size() < block && grp[y].size() < block) {
            int p = 0;
            for (int j = 0; j < grp[y].size(); j++) {
                while (p < grp[x].size() && tout[grp[x][p]] < tin[grp[y][j]]) p++;
                ans += tout[grp[x][p]] >= tin[grp[y][j]] && tin[grp[x][p]] <= tin[grp[y][j]];
            }
            cout << ans << endl;
        }
        else if (grp[x].size() < block && grp[y].size() >= block) {
            vector<pii> v;
            for (int val : grp[x]) {
                if (v.empty() || v.back().second < tin[val]) v.push_back({tin[val], tout[val]});
                else v.back().second = max(v.back().second,tout[val]);
            }
            for (pii val : v) {
                ans += large[pos[y]][val.second] - large[pos[y]][val.first-1];
            }
            cout << ans << endl;
        }
        else {
            for (int v : grp[y]) {
                ans += control[pos[x]][tin[v]];
            }
            cout << ans << endl;
        }
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void solve()':
regions.cpp:42:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |         if (grp[i].size() >= block) {
      |             ~~~~~~~~~~~~~~^~~~~~~~
regions.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < pre.size(); i++) {
      |                     ~~^~~~~~~~~~~~
regions.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j = 0; j < pre.size(); j++) {
      |                         ~~^~~~~~~~~~~~
regions.cpp:69:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         if (grp[x].size() >= block && grp[y].size() >= block) {
      |             ~~~~~~~~~~~~~~^~~~~~~~
regions.cpp:69:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         if (grp[x].size() >= block && grp[y].size() >= block) {
      |                                       ~~~~~~~~~~~~~~^~~~~~~~
regions.cpp:72:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |         else if (grp[x].size() < block && grp[y].size() < block) {
      |                  ~~~~~~~~~~~~~~^~~~~~~
regions.cpp:72:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |         else if (grp[x].size() < block && grp[y].size() < block) {
      |                                           ~~~~~~~~~~~~~~^~~~~~~
regions.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for (int j = 0; j < grp[y].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~
regions.cpp:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 while (p < grp[x].size() && tout[grp[x][p]] < tin[grp[y][j]]) p++;
      |                        ~~^~~~~~~~~~~~~~~
regions.cpp:80:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         else if (grp[x].size() < block && grp[y].size() >= block) {
      |                  ~~~~~~~~~~~~~~^~~~~~~
regions.cpp:80:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         else if (grp[x].size() < block && grp[y].size() >= block) {
      |                                           ~~~~~~~~~~~~~~^~~~~~~~

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