Submission #523514

# Submission time Handle Problem Language Result Execution time Memory
523514 2022-02-07T17:56:56 Z Vladth11 Regions (IOI09_regions) C++14
20 / 100
1262 ms 56764 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 = 200;
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
            preorder[timp[x].second + 1]--;
        }
        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:115: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]
  115 |             while(i < lista[a].size() && j < lista[b].size()) {
      |                   ~~^~~~~~~~~~~~~~~~~
regions.cpp:115: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]
  115 |             while(i < lista[a].size() && j < lista[b].size()) {
      |                                          ~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 8 ms 14408 KB Output is correct
2 Correct 8 ms 14348 KB Output is correct
3 Correct 9 ms 14408 KB Output is correct
4 Correct 11 ms 14536 KB Output is correct
5 Correct 12 ms 14664 KB Output is correct
6 Correct 25 ms 16072 KB Output is correct
7 Correct 46 ms 15304 KB Output is correct
8 Correct 38 ms 15740 KB Output is correct
9 Correct 68 ms 17172 KB Output is correct
10 Correct 87 ms 18364 KB Output is correct
11 Correct 127 ms 17228 KB Output is correct
12 Correct 169 ms 19776 KB Output is correct
13 Correct 184 ms 18752 KB Output is correct
14 Correct 168 ms 18028 KB Output is correct
15 Correct 219 ms 23280 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 889 ms 22760 KB Output isn't correct
2 Incorrect 903 ms 22264 KB Output isn't correct
3 Correct 1262 ms 25296 KB Output is correct
4 Runtime error 63 ms 40724 KB Execution killed with signal 11
5 Runtime error 71 ms 41192 KB Execution killed with signal 11
6 Runtime error 84 ms 42668 KB Execution killed with signal 11
7 Runtime error 91 ms 44444 KB Execution killed with signal 11
8 Runtime error 104 ms 46916 KB Execution killed with signal 11
9 Runtime error 166 ms 51824 KB Execution killed with signal 11
10 Runtime error 186 ms 53848 KB Execution killed with signal 11
11 Runtime error 181 ms 56764 KB Execution killed with signal 11
12 Runtime error 193 ms 54504 KB Execution killed with signal 11
13 Runtime error 196 ms 54528 KB Execution killed with signal 11
14 Runtime error 175 ms 55676 KB Execution killed with signal 11
15 Runtime error 185 ms 55988 KB Execution killed with signal 11
16 Runtime error 206 ms 56008 KB Execution killed with signal 11
17 Runtime error 185 ms 55732 KB Execution killed with signal 11