oj.uz

답안 #523480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523480 2022-02-07T17:30:30 Z Vladth11 Regions (IOI09_regions) C++14
0 / 100
 174 ms 29752 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[501][MMAX];
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 500 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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 19528 KB Execution killed with signal 11
2 Runtime error 21 ms 19528 KB Execution killed with signal 11
3 Runtime error 21 ms 19528 KB Execution killed with signal 11
4 Runtime error 21 ms 19528 KB Execution killed with signal 11
5 Runtime error 21 ms 19528 KB Execution killed with signal 11
6 Runtime error 24 ms 19504 KB Execution killed with signal 11
7 Runtime error 24 ms 19520 KB Execution killed with signal 11
8 Runtime error 23 ms 19528 KB Execution killed with signal 11
9 Runtime error 23 ms 19712 KB Execution killed with signal 11
10 Runtime error 27 ms 20000 KB Execution killed with signal 11
11 Runtime error 30 ms 20160 KB Execution killed with signal 11
12 Runtime error 33 ms 20364 KB Execution killed with signal 11
13 Runtime error 34 ms 20544 KB Execution killed with signal 11
14 Runtime error 38 ms 20932 KB Execution killed with signal 11
15 Runtime error 44 ms 21264 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 63 ms 22860 KB Execution killed with signal 11
2 Runtime error 73 ms 23096 KB Execution killed with signal 11
3 Runtime error 74 ms 23452 KB Execution killed with signal 11
4 Runtime error 39 ms 21056 KB Execution killed with signal 11
5 Runtime error 43 ms 21344 KB Execution killed with signal 11
6 Runtime error 63 ms 22028 KB Execution killed with signal 11
7 Runtime error 72 ms 22956 KB Execution killed with signal 11
8 Runtime error 81 ms 24384 KB Execution killed with signal 11
9 Runtime error 115 ms 27020 KB Execution killed with signal 11
10 Runtime error 151 ms 28244 KB Execution killed with signal 11
11 Runtime error 147 ms 29752 KB Execution killed with signal 11
12 Runtime error 140 ms 28552 KB Execution killed with signal 11
13 Runtime error 142 ms 28536 KB Execution killed with signal 11
14 Runtime error 174 ms 29252 KB Execution killed with signal 11
15 Runtime error 153 ms 29488 KB Execution killed with signal 11
16 Runtime error 157 ms 29400 KB Execution killed with signal 11
17 Runtime error 159 ms 29276 KB Execution killed with signal 11