oj.uz

Submission #523431

# Submission time Handle Problem Language Result Execution time Memory
523431 2022-02-07T16:04:43 Z Vladth11 Regions (IOI09_regions) C++14
25 / 100
 2060 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 <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 = 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;
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 <= MMAX; 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(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]] += 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()) {
      |                                          ~~^~~~~~~~~~~~~~~~~
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]] += 1LL * 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 11 ms 17096 KB Output is correct
2 Correct 10 ms 17096 KB Output is correct
3 Correct 12 ms 17224 KB Output is correct
4 Correct 14 ms 17352 KB Output is correct
5 Correct 12 ms 17352 KB Output is correct
6 Correct 29 ms 18504 KB Output is correct
7 Correct 39 ms 17992 KB Output is correct
8 Correct 34 ms 18248 KB Output is correct
9 Correct 61 ms 19400 KB Output is correct
10 Correct 106 ms 19912 KB Output is correct
11 Correct 145 ms 19648 KB Output is correct
12 Correct 148 ms 21244 KB Output is correct
13 Correct 169 ms 20800 KB Output is correct
14 Correct 260 ms 20504 KB Output is correct
15 Correct 305 ms 24596 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 897 ms 25592 KB Output isn't correct
2 Incorrect 1234 ms 25420 KB Output isn't correct
3 Incorrect 2060 ms 28708 KB Output isn't correct
4 Correct 484 ms 39488 KB Output is correct
5 Correct 433 ms 46652 KB Output is correct
6 Incorrect 782 ms 83392 KB Output isn't correct
7 Incorrect 1321 ms 115836 KB Output isn't correct
8 Incorrect 1630 ms 126896 KB Output isn't correct
9 Runtime error 1217 ms 131076 KB Execution killed with signal 9
10 Runtime error 200 ms 131076 KB Execution killed with signal 9
11 Runtime error 191 ms 131076 KB Execution killed with signal 9
12 Runtime error 1507 ms 131076 KB Execution killed with signal 9
13 Runtime error 1592 ms 131076 KB Execution killed with signal 9
14 Runtime error 1411 ms 131076 KB Execution killed with signal 9
15 Runtime error 193 ms 131076 KB Execution killed with signal 9
16 Runtime error 202 ms 131076 KB Execution killed with signal 9
17 Runtime error 682 ms 131076 KB Execution killed with signal 9