oj.uz

Submission #521843

# Submission time Handle Problem Language Result Execution time Memory
521843 2022-02-03T09:53:12 Z Vladth11 Regions (IOI09_regions) C++14
25 / 100
 2862 ms 131076 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 int NMAX = 200001;
const int VMAX = 21;
const int INF = (1LL << 60);
const int MOD = 1000000007;
const int BLOCK = 318;
const int base = 31;
const int nr_of_bits = 21;
const int MMAX = NMAX / BLOCK + 5;

vector <int> v[NMAX], vertices[NMAX];
vector <pii> lista[NMAX];
int stamp;
int n, R, Q;
int sol[MMAX][25001];
int 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 <= MMAX; i++) {
        sol[i][region[node]] += countAbove[i];
    }
    for(auto x : v[node]) {
        if(x == p)
            continue;
        DFS(x, 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(i);
    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] = 1;
            preorder[timp[x].second + 1] = -1;
        }
        for(int j = 1; j <= n; j++) {
            preorder[j] += preorder[j - 1];
        }
        for(int j = 1; j <= sc; j++) {
            for(auto x : vertices[j])
                precalc[j][bigIdx[i]] += (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:112:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while(i < lista[a].size() && j < lista[b].size()) {
      |                   ~~^~~~~~~~~~~~~~~~~
regions.cpp:112:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while(i < lista[a].size() && j < lista[b].size()) {
      |                                          ~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'void DFS(int, int)':
regions.cpp:46:30: warning: iteration 632 invokes undefined behavior [-Waggressive-loop-optimizations]
   46 |         sol[i][region[node]] += countAbove[i];
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
regions.cpp:45:22: note: within this loop
   45 |     for(int i = 1; i <= MMAX; i++) {
      |                    ~~^~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16968 KB Output is correct
2 Correct 10 ms 17036 KB Output is correct
3 Correct 11 ms 17096 KB Output is correct
4 Correct 12 ms 17096 KB Output is correct
5 Correct 16 ms 17216 KB Output is correct
6 Correct 30 ms 17864 KB Output is correct
7 Correct 33 ms 17564 KB Output is correct
8 Correct 48 ms 17736 KB Output is correct
9 Correct 61 ms 18760 KB Output is correct
10 Correct 89 ms 19144 KB Output is correct
11 Correct 145 ms 19268 KB Output is correct
12 Correct 172 ms 20712 KB Output is correct
13 Correct 175 ms 20672 KB Output is correct
14 Correct 229 ms 21104 KB Output is correct
15 Correct 319 ms 25896 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 919 ms 26928 KB Output isn't correct
2 Incorrect 1233 ms 26484 KB Output isn't correct
3 Incorrect 1863 ms 30568 KB Output isn't correct
4 Correct 402 ms 30572 KB Output is correct
5 Correct 576 ms 35596 KB Output is correct
6 Incorrect 979 ms 56488 KB Output isn't correct
7 Incorrect 1422 ms 74560 KB Output isn't correct
8 Incorrect 1570 ms 83052 KB Output isn't correct
9 Incorrect 2862 ms 108656 KB Output isn't correct
10 Runtime error 1233 ms 131076 KB Execution killed with signal 9
11 Runtime error 1474 ms 131076 KB Execution killed with signal 9
12 Incorrect 2348 ms 113680 KB Output isn't correct
13 Incorrect 2746 ms 115316 KB Output isn't correct
14 Runtime error 1421 ms 131076 KB Execution killed with signal 9
15 Runtime error 1438 ms 131076 KB Execution killed with signal 9
16 Runtime error 1492 ms 131076 KB Execution killed with signal 9
17 Runtime error 1365 ms 131076 KB Execution killed with signal 9