oj.uz

Submission #523443

# Submission time Handle Problem Language Result Execution time Memory
523443 2022-02-07T16:17:15 Z Vladth11 Regions (IOI09_regions) C++14
1 / 100
 8000 ms 33092 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 = 1;
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][5];
ll precalc[5][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[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()) {
      |                                          ~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'void DFS(int, int)':
regions.cpp:46:30: warning: iteration 200005 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
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22256 KB Output is correct
2 Incorrect 18 ms 22272 KB Output isn't correct
3 Incorrect 36 ms 22264 KB Output isn't correct
4 Incorrect 99 ms 22240 KB Output isn't correct
5 Incorrect 231 ms 22396 KB Output isn't correct
6 Incorrect 439 ms 22288 KB Output isn't correct
7 Incorrect 704 ms 22356 KB Output isn't correct
8 Incorrect 1046 ms 22384 KB Output isn't correct
9 Incorrect 2394 ms 23104 KB Output isn't correct
10 Incorrect 5125 ms 22928 KB Output isn't correct
11 Incorrect 6682 ms 23380 KB Output isn't correct
12 Execution timed out 8045 ms 24160 KB Time limit exceeded
13 Execution timed out 8098 ms 23844 KB Time limit exceeded
14 Execution timed out 8035 ms 24560 KB Time limit exceeded
15 Execution timed out 8031 ms 25700 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8082 ms 26348 KB Time limit exceeded
2 Execution timed out 8087 ms 26440 KB Time limit exceeded
3 Execution timed out 8077 ms 28008 KB Time limit exceeded
4 Execution timed out 8034 ms 24664 KB Time limit exceeded
5 Execution timed out 8044 ms 26040 KB Time limit exceeded
6 Execution timed out 8071 ms 25980 KB Time limit exceeded
7 Execution timed out 8071 ms 26720 KB Time limit exceeded
8 Execution timed out 8100 ms 28492 KB Time limit exceeded
9 Execution timed out 8096 ms 30500 KB Time limit exceeded
10 Execution timed out 8071 ms 31860 KB Time limit exceeded
11 Execution timed out 8035 ms 32564 KB Time limit exceeded
12 Execution timed out 8067 ms 31436 KB Time limit exceeded
13 Execution timed out 8090 ms 31784 KB Time limit exceeded
14 Execution timed out 8055 ms 32168 KB Time limit exceeded
15 Execution timed out 8058 ms 33092 KB Time limit exceeded
16 Execution timed out 8095 ms 32844 KB Time limit exceeded
17 Execution timed out 8009 ms 32452 KB Time limit exceeded