oj.uz

Submission #523474

# Submission time Handle Problem Language Result Execution time Memory
523474 2022-02-07T17:22:19 Z Vladth11 Regions (IOI09_regions) C++14
1 / 100
 8000 ms 33464 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 = 0;
const int base = 31;
const int nr_of_bits = 21;
const int MMAX = NMAX / 1 + 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(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] = 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 17 ms 22252 KB Output is correct
2 Incorrect 19 ms 22216 KB Output isn't correct
3 Incorrect 41 ms 22236 KB Output isn't correct
4 Incorrect 96 ms 22216 KB Output isn't correct
5 Incorrect 190 ms 22256 KB Output isn't correct
6 Incorrect 398 ms 22312 KB Output isn't correct
7 Incorrect 571 ms 22360 KB Output isn't correct
8 Incorrect 1022 ms 22448 KB Output isn't correct
9 Incorrect 2040 ms 22996 KB Output isn't correct
10 Incorrect 4078 ms 23104 KB Output isn't correct
11 Incorrect 7018 ms 23348 KB Output isn't correct
12 Execution timed out 8089 ms 23976 KB Time limit exceeded
13 Execution timed out 8077 ms 23872 KB Time limit exceeded
14 Execution timed out 8085 ms 24168 KB Time limit exceeded
15 Execution timed out 8071 ms 25892 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8077 ms 26252 KB Time limit exceeded
2 Execution timed out 8074 ms 26516 KB Time limit exceeded
3 Execution timed out 8052 ms 28080 KB Time limit exceeded
4 Execution timed out 8071 ms 24684 KB Time limit exceeded
5 Execution timed out 8074 ms 25724 KB Time limit exceeded
6 Execution timed out 8079 ms 25796 KB Time limit exceeded
7 Execution timed out 8032 ms 26608 KB Time limit exceeded
8 Execution timed out 8048 ms 28600 KB Time limit exceeded
9 Execution timed out 8053 ms 30696 KB Time limit exceeded
10 Execution timed out 8084 ms 32036 KB Time limit exceeded
11 Execution timed out 8036 ms 32604 KB Time limit exceeded
12 Execution timed out 8013 ms 31528 KB Time limit exceeded
13 Execution timed out 8037 ms 31600 KB Time limit exceeded
14 Execution timed out 8036 ms 32024 KB Time limit exceeded
15 Execution timed out 8015 ms 33464 KB Time limit exceeded
16 Execution timed out 8009 ms 33136 KB Time limit exceeded
17 Execution timed out 8039 ms 32736 KB Time limit exceeded