Submission #523521

# Submission time Handle Problem Language Result Execution time Memory
523521 2022-02-07T18:03:25 Z Vladth11 Regions (IOI09_regions) C++14
30 / 100
1954 ms 51680 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 <int, int> pii;
typedef pair <long double, pii> muchie;

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

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

void DFS(int node, int p) {
    stamp++;
    timp[node].first = ++timestamp;
    lista[region[node]].push_back({node, stamp});
    if(bigIdx[region[node]] != 0) {
        countAbove[bigIdx[region[node]]]++;
    }
    for(int 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() {
    int i;
    cin >> n >> R >> Q;
    cin >> region[1];
    vertices[region[1]].push_back(1);
    cati[region[1]]++;
    for(i = 2; i <= n; i++) {
        int p;
        cin >> p >> region[i];
        v[p].push_back(i);
        v[i].push_back(p);
        vertices[region[i]].push_back(i);
        cati[region[i]]++;
    }
    int 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(int i = 1; i <= R; i++) {
        if(bigIdx[i] == 0) continue;
        for(auto x : vertices[i]) {
            preorder[timp[x].first]++; /// BRUH
        }
        for(int j = 1; j <= n; j++) {
            preorder[j] += preorder[j - 1];
        }
        for(int 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(int j = 1; j <= n; j++)
            preorder[j] = 0;
    }
    while(Q--) {
        int 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
            int i = 0;
            int j = 0;
            int deschise = 0;
            vf = 0;
            int 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(stiva[vf] == x.first) {
                        vf--;
                        deschise--;
                    } else {
                        stiva[++vf] = x.first;
                        deschise++;
                    }
                    i++;
                } else {
                    if(stiva[vf] == y.first) {
                        vf--;
                    } else {
                        rez += deschise;
                        stiva[++vf] = y.first;
                    }
                    j++;
                }
            }
            cout << rez;
        }
        cout << endl;
    }
    return 0;
}

Compilation message

regions.cpp:12:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   12 | const int INF = (1LL << 60);
      |                 ~~~~~^~~~~~
regions.cpp: In function 'int main()':
regions.cpp:114:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, 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: 'int' and 'std::vector<std::pair<int, 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 8 ms 14336 KB Output is correct
2 Correct 8 ms 14368 KB Output is correct
3 Correct 9 ms 14408 KB Output is correct
4 Correct 12 ms 14536 KB Output is correct
5 Correct 15 ms 14580 KB Output is correct
6 Correct 28 ms 16120 KB Output is correct
7 Correct 33 ms 15304 KB Output is correct
8 Correct 36 ms 15688 KB Output is correct
9 Correct 46 ms 17224 KB Output is correct
10 Correct 124 ms 18372 KB Output is correct
11 Correct 108 ms 17224 KB Output is correct
12 Correct 165 ms 19708 KB Output is correct
13 Correct 190 ms 18716 KB Output is correct
14 Correct 215 ms 17952 KB Output is correct
15 Correct 229 ms 22144 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1116 ms 22920 KB Output is correct
2 Correct 892 ms 22676 KB Output is correct
3 Correct 1954 ms 26200 KB Output is correct
4 Runtime error 47 ms 35752 KB Execution killed with signal 11
5 Runtime error 59 ms 36216 KB Execution killed with signal 11
6 Runtime error 89 ms 37692 KB Execution killed with signal 11
7 Runtime error 75 ms 39428 KB Execution killed with signal 11
8 Runtime error 96 ms 41996 KB Execution killed with signal 11
9 Runtime error 158 ms 46592 KB Execution killed with signal 11
10 Runtime error 156 ms 48976 KB Execution killed with signal 11
11 Runtime error 163 ms 51680 KB Execution killed with signal 11
12 Runtime error 179 ms 49404 KB Execution killed with signal 11
13 Runtime error 168 ms 49436 KB Execution killed with signal 11
14 Runtime error 165 ms 50748 KB Execution killed with signal 11
15 Runtime error 164 ms 50992 KB Execution killed with signal 11
16 Runtime error 227 ms 50752 KB Execution killed with signal 11
17 Runtime error 163 ms 50764 KB Execution killed with signal 11