oj.uz

답안 #521842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521842 2022-02-03T09:47:31 Z Vladth11 Regions (IOI09_regions) C++14
0 / 100
 1682 ms 131076 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 <ll, ll> 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 = 318;
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;
int sol[MMAX][25001];
int precalc[25001][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]] += countAbove[i];
    }
    for(auto x : v[node]) {
        if(x == p)
            continue;
        DFS(x, node);
    }
    stamp++;
    timp[node].second = timestamp;
    lista[region[node]].push_back({node, stamp});
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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]] += (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.flush();
    }
    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<long long int, long long 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<long long int, long long 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 632 invokes undefined behavior [-Waggressive-loop-optimizations]
   46 |         sol[i][region[node]] += 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 Execution timed out 8 ms 17096 KB Time limit exceeded (wall clock)
2 Execution timed out 8 ms 17096 KB Time limit exceeded (wall clock)
3 Execution timed out 8 ms 17096 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 17096 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 17224 KB Time limit exceeded (wall clock)
6 Execution timed out 10 ms 17920 KB Time limit exceeded (wall clock)
7 Execution timed out 10 ms 17608 KB Time limit exceeded (wall clock)
8 Execution timed out 10 ms 17736 KB Time limit exceeded (wall clock)
9 Execution timed out 13 ms 18888 KB Time limit exceeded (wall clock)
10 Execution timed out 19 ms 19144 KB Time limit exceeded (wall clock)
11 Execution timed out 26 ms 19396 KB Time limit exceeded (wall clock)
12 Execution timed out 31 ms 20800 KB Time limit exceeded (wall clock)
13 Execution timed out 41 ms 20724 KB Time limit exceeded (wall clock)
14 Execution timed out 40 ms 21056 KB Time limit exceeded (wall clock)
15 Execution timed out 54 ms 25880 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 97 ms 26928 KB Time limit exceeded (wall clock)
2 Execution timed out 103 ms 26540 KB Time limit exceeded (wall clock)
3 Execution timed out 121 ms 30512 KB Time limit exceeded (wall clock)
4 Execution timed out 172 ms 30476 KB Time limit exceeded (wall clock)
5 Execution timed out 222 ms 35768 KB Time limit exceeded (wall clock)
6 Execution timed out 330 ms 56532 KB Time limit exceeded (wall clock)
7 Execution timed out 476 ms 74644 KB Time limit exceeded (wall clock)
8 Execution timed out 638 ms 82940 KB Time limit exceeded (wall clock)
9 Execution timed out 972 ms 108704 KB Time limit exceeded (wall clock)
10 Runtime error 1146 ms 131076 KB Execution killed with signal 9
11 Runtime error 1328 ms 131076 KB Execution killed with signal 9
12 Execution timed out 1223 ms 113760 KB Time limit exceeded (wall clock)
13 Execution timed out 1213 ms 115564 KB Time limit exceeded (wall clock)
14 Runtime error 1436 ms 131076 KB Execution killed with signal 9
15 Runtime error 1443 ms 131076 KB Execution killed with signal 9
16 Runtime error 1432 ms 131076 KB Execution killed with signal 9
17 Runtime error 1682 ms 131076 KB Execution killed with signal 9