Submission #523541

# Submission time Handle Problem Language Result Execution time Memory
523541 2022-02-07T18:12:52 Z Vladth11 Regions (IOI09_regions) C++14
30 / 100
1467 ms 40352 KB
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 200001;
const ll VMAX = 21;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 100;
const ll base = 31;
const ll nr_of_bits = 21;
const ll MMAX = NMAX / BLOCK + 2;

vector <ll> v[NMAX], vertices[NMAX];
vector <pii> lista[NMAX];
ll stamp;
ll n, R, Q;
ll sol[MMAX][25001];
ll precalc[25001][MMAX];
ll region[NMAX];
ll bigR[NMAX];
ll smallR[NMAX];
ll bigIdx[NMAX];
ll smallIdx[NMAX];
ll cati[NMAX];
ll stiva[NMAX];
ll vf;
ll countAbove[MMAX];
ll timestamp;
pii timp[NMAX];
ll preorder[NMAX + 1];

void DFS(ll node, ll p) {
    stamp++;
    timp[node].first = ++timestamp;
    lista[region[node]].push_back({node, stamp});
    if(bigIdx[region[node]] != 0) {
        countAbove[bigIdx[region[node]]]++;
    }
    for(ll i = 1; i <= R; i++) {
        sol[i][region[node]] += 1LL * countAbove[i];
    }
    for(auto x : v[node]) {
        if(x == p)
            continue;
        DFS(x, node);
    }
    if(bigIdx[region[node]] != 0) {
        countAbove[bigIdx[region[node]]]--;
    }
    stamp++;
    timp[node].second = timestamp;
    lista[region[node]].push_back({node, stamp});
}

int main() {
    ll i;
    cin >> n >> R >> Q;
    cin >> region[1];
    vertices[region[1]].push_back(1);
    cati[region[1]]++;
    for(i = 2; i <= n; i++) {
        ll p;
        cin >> p >> region[i];
        v[p].push_back(i);
        v[i].push_back(p);
        vertices[region[i]].push_back(i);
        cati[region[i]]++;
    }
    ll cc = 0, sc = 0;
    for(i = 1; i <= R; i++) {
        if(cati[i] >= BLOCK) {
            bigR[++cc] = i;
            bigIdx[i] = cc;
        } else {
            smallR[++sc] = i;
            smallIdx[i] = sc;
        }
    }
    DFS(1, 0);
    for(ll i = 1; i <= R; i++) {
        if(bigIdx[i] == 0) continue;
        for(auto x : vertices[i]) {
            preorder[timp[x].first]++; /// BRUH
        }
        for(ll j = 1; j <= n; j++) {
            preorder[j] += preorder[j - 1];
        }
        for(ll j = 1; j <= sc; j++) {
            for(auto x : vertices[smallR[j]])
                precalc[j][bigIdx[i]] += 1LL * (preorder[timp[x].second] - preorder[timp[x].first - 1]);
        }
        for(ll j = 1; j <= n; j++)
            preorder[j] = 0;
    }
    while(Q--) {
        ll a, b;
        cin >> a >> b;
        if(bigIdx[a] != 0) { /// Aia de sus mare
            cout << sol[bigIdx[a]][b] << "\n";
        } else if(bigIdx[b] != 0) { /// Aia de jos mare si aia de sus mica
            cout << precalc[smallIdx[a]][bigIdx[b]] << "\n";
        } else { /// Ambele mici
            ll i = 0;
            ll j = 0;
            ll deschise = 0;
            vf = 0;
            ll rez = 0;
            while(i < lista[a].size() && j < lista[b].size()) {
                pii x = lista[a][i];
                pii y = lista[b][j];
                if(x.second < y.second) {
                    if(vf && stiva[vf] == x.first) {
                        vf--;
                        deschise--;
                    } else {
                        stiva[++vf] = x.first;
                        deschise++;
                    }
                    i++;
                } else {
                    if(vf && stiva[vf] == y.first) {
                        vf--;
                    } else {
                        rez += deschise;
                        stiva[++vf] = y.first;
                    }
                    j++;
                }
            }
            cout << rez;
        }
        cout << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:114:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             while(i < lista[a].size() && j < lista[b].size()) {
      |                   ~~^~~~~~~~~~~~~~~~~
regions.cpp:114:44: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             while(i < lista[a].size() && j < lista[b].size()) {
      |                                          ~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14408 KB Output is correct
2 Correct 7 ms 14408 KB Output is correct
3 Correct 10 ms 14536 KB Output is correct
4 Correct 14 ms 14604 KB Output is correct
5 Correct 18 ms 14664 KB Output is correct
6 Correct 30 ms 16200 KB Output is correct
7 Correct 42 ms 15432 KB Output is correct
8 Correct 49 ms 15816 KB Output is correct
9 Correct 65 ms 17532 KB Output is correct
10 Correct 140 ms 18836 KB Output is correct
11 Correct 116 ms 17864 KB Output is correct
12 Correct 198 ms 20656 KB Output is correct
13 Correct 219 ms 20008 KB Output is correct
14 Correct 187 ms 19764 KB Output is correct
15 Correct 231 ms 24868 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 981 ms 25592 KB Output is correct
2 Correct 834 ms 25812 KB Output is correct
3 Correct 1467 ms 29388 KB Output is correct
4 Runtime error 46 ms 27812 KB Execution killed with signal 11
5 Runtime error 49 ms 28204 KB Execution killed with signal 11
6 Runtime error 61 ms 29276 KB Execution killed with signal 11
7 Runtime error 90 ms 30700 KB Execution killed with signal 11
8 Runtime error 83 ms 32228 KB Execution killed with signal 11
9 Runtime error 123 ms 36056 KB Execution killed with signal 11
10 Runtime error 141 ms 37452 KB Execution killed with signal 11
11 Runtime error 178 ms 40352 KB Execution killed with signal 11
12 Runtime error 168 ms 37872 KB Execution killed with signal 11
13 Runtime error 173 ms 38152 KB Execution killed with signal 11
14 Runtime error 172 ms 39148 KB Execution killed with signal 11
15 Runtime error 175 ms 39008 KB Execution killed with signal 11
16 Runtime error 172 ms 38728 KB Execution killed with signal 11
17 Runtime error 169 ms 38744 KB Execution killed with signal 11