oj.uz

Submission #523451

# Submission time Handle Problem Language Result Execution time Memory
523451 2022-02-07T16:29:21 Z Vladth11 Regions (IOI09_regions) C++14
1 / 100
 8000 ms 33312 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(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 19 ms 22216 KB Output is correct
2 Incorrect 20 ms 22132 KB Output isn't correct
3 Incorrect 33 ms 22216 KB Output isn't correct
4 Incorrect 74 ms 22240 KB Output isn't correct
5 Incorrect 232 ms 22268 KB Output isn't correct
6 Incorrect 415 ms 22432 KB Output isn't correct
7 Incorrect 774 ms 22468 KB Output isn't correct
8 Incorrect 877 ms 22620 KB Output isn't correct
9 Incorrect 2116 ms 23016 KB Output isn't correct
10 Incorrect 4207 ms 23104 KB Output isn't correct
11 Incorrect 5835 ms 23516 KB Output isn't correct
12 Execution timed out 8050 ms 24272 KB Time limit exceeded
13 Execution timed out 8048 ms 24272 KB Time limit exceeded
14 Execution timed out 8022 ms 24444 KB Time limit exceeded
15 Execution timed out 8035 ms 26024 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8028 ms 26436 KB Time limit exceeded
2 Execution timed out 8048 ms 26496 KB Time limit exceeded
3 Execution timed out 8061 ms 28100 KB Time limit exceeded
4 Execution timed out 8079 ms 24596 KB Time limit exceeded
5 Execution timed out 8041 ms 25744 KB Time limit exceeded
6 Execution timed out 8036 ms 26008 KB Time limit exceeded
7 Execution timed out 8061 ms 26684 KB Time limit exceeded
8 Execution timed out 8082 ms 28248 KB Time limit exceeded
9 Execution timed out 8095 ms 30280 KB Time limit exceeded
10 Execution timed out 8099 ms 31912 KB Time limit exceeded
11 Execution timed out 8070 ms 32540 KB Time limit exceeded
12 Execution timed out 8085 ms 31324 KB Time limit exceeded
13 Execution timed out 8096 ms 31784 KB Time limit exceeded
14 Execution timed out 8071 ms 32044 KB Time limit exceeded
15 Execution timed out 8039 ms 33312 KB Time limit exceeded
16 Execution timed out 8035 ms 33300 KB Time limit exceeded
17 Execution timed out 8093 ms 32784 KB Time limit exceeded