oj.uz

Submission #523434

# Submission time Handle Problem Language Result Execution time Memory
523434 2022-02-07T16:06:07 Z Vladth11 Regions (IOI09_regions) C++14
1 / 100
 8000 ms 33100 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[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 19 ms 22216 KB Output is correct
2 Incorrect 23 ms 22216 KB Output isn't correct
3 Incorrect 40 ms 22256 KB Output isn't correct
4 Incorrect 83 ms 22236 KB Output isn't correct
5 Incorrect 218 ms 22264 KB Output isn't correct
6 Incorrect 346 ms 22296 KB Output isn't correct
7 Incorrect 725 ms 22308 KB Output isn't correct
8 Incorrect 1105 ms 22620 KB Output isn't correct
9 Incorrect 2516 ms 23016 KB Output isn't correct
10 Incorrect 4912 ms 23228 KB Output isn't correct
11 Incorrect 6563 ms 23836 KB Output isn't correct
12 Execution timed out 8055 ms 24272 KB Time limit exceeded
13 Execution timed out 8061 ms 23968 KB Time limit exceeded
14 Execution timed out 8042 ms 24476 KB Time limit exceeded
15 Execution timed out 8074 ms 25816 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8055 ms 26488 KB Time limit exceeded
2 Execution timed out 8034 ms 26440 KB Time limit exceeded
3 Execution timed out 8073 ms 27712 KB Time limit exceeded
4 Execution timed out 8055 ms 24424 KB Time limit exceeded
5 Execution timed out 8077 ms 25432 KB Time limit exceeded
6 Execution timed out 8060 ms 25736 KB Time limit exceeded
7 Execution timed out 8085 ms 26420 KB Time limit exceeded
8 Execution timed out 8077 ms 28272 KB Time limit exceeded
9 Execution timed out 8054 ms 30148 KB Time limit exceeded
10 Execution timed out 8090 ms 31788 KB Time limit exceeded
11 Execution timed out 8042 ms 32428 KB Time limit exceeded
12 Execution timed out 8071 ms 31416 KB Time limit exceeded
13 Execution timed out 8090 ms 31736 KB Time limit exceeded
14 Execution timed out 8096 ms 32116 KB Time limit exceeded
15 Execution timed out 8052 ms 33048 KB Time limit exceeded
16 Execution timed out 8093 ms 33100 KB Time limit exceeded
17 Execution timed out 8048 ms 32696 KB Time limit exceeded