Submission #523496

# Submission time Handle Problem Language Result Execution time Memory
523496 2022-02-07T17:44:23 Z Vladth11 Regions (IOI09_regions) C++14
25 / 100
3630 ms 80160 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 = 400005;
const int VMAX = 21;
const int INF = (1LL << 60);
const int MOD = 1000000007;
const int BLOCK = 447;
const int base = 31;
const int nr_of_bits = 21;
const int MMAX = 500;
 
vector <int> v[NMAX], vertices[NMAX];
vector <pii> lista[NMAX];
int stamp;
int n, R, Q;
ll sol[501][501];
ll precalc[501][501];
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 <= R; 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]++; /// BRUH
            preorder[timp[x].second + 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()) {
      |                                          ~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 18 ms 28452 KB Output is correct
2 Correct 15 ms 28488 KB Output is correct
3 Correct 17 ms 28488 KB Output is correct
4 Correct 25 ms 28588 KB Output is correct
5 Correct 21 ms 28724 KB Output is correct
6 Correct 32 ms 29632 KB Output is correct
7 Correct 39 ms 29128 KB Output is correct
8 Correct 44 ms 29444 KB Output is correct
9 Correct 67 ms 30488 KB Output is correct
10 Correct 99 ms 30920 KB Output is correct
11 Correct 128 ms 30752 KB Output is correct
12 Correct 189 ms 32132 KB Output is correct
13 Correct 218 ms 31776 KB Output is correct
14 Correct 185 ms 31680 KB Output is correct
15 Correct 320 ms 35700 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 1098 ms 36688 KB Output isn't correct
2 Incorrect 946 ms 36416 KB Output isn't correct
3 Incorrect 1885 ms 39744 KB Output isn't correct
4 Correct 1338 ms 33056 KB Output is correct
5 Correct 1968 ms 35232 KB Output is correct
6 Runtime error 3630 ms 74208 KB Execution killed with signal 11
7 Runtime error 89 ms 67972 KB Execution killed with signal 11
8 Runtime error 114 ms 70380 KB Execution killed with signal 11
9 Runtime error 148 ms 74976 KB Execution killed with signal 11
10 Runtime error 178 ms 77176 KB Execution killed with signal 11
11 Runtime error 184 ms 80160 KB Execution killed with signal 11
12 Runtime error 186 ms 77820 KB Execution killed with signal 11
13 Runtime error 178 ms 77844 KB Execution killed with signal 11
14 Runtime error 175 ms 78960 KB Execution killed with signal 11
15 Runtime error 189 ms 79232 KB Execution killed with signal 11
16 Runtime error 186 ms 79068 KB Execution killed with signal 11
17 Runtime error 222 ms 78960 KB Execution killed with signal 11