| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 523427 | 2022-02-07T16:02:41 Z | Vladth11 | Regions (IOI09_regions) | C++14 | 1573 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 ll NMAX = 200001;
const ll VMAX = 21;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;
const ll MMAX = NMAX / BLOCK + 5;
vector <ll> v[NMAX], vertices[NMAX];
vector <pii> lista[NMAX];
ll stamp;
ll n, R, Q;
ll sol[MMAX][25001];
ll precalc[25001][MMAX];
ll region[NMAX];
ll bigR[NMAX];
ll smallR[NMAX];
ll bigIdx[NMAX];
ll smallIdx[NMAX];
ll cati[NMAX];
ll stiva[NMAX];
ll vf;
ll countAbove[MMAX];
ll timestamp;
pii timp[NMAX];
ll preorder[NMAX + 1];
void DFS(ll node, ll p) {
stamp++;
timp[node].first = ++timestamp;
lista[region[node]].push_back({node, stamp});
if(bigIdx[region[node]] != 0) {
countAbove[bigIdx[region[node]]]++;
}
for(ll i = 1; i <= MMAX; i++) {
sol[i][region[node]] += 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() {
ll i;
cin >> n >> R >> Q;
cin >> region[1];
vertices[region[1]].push_back(i);
cati[region[1]]++;
for(i = 2; i <= n; i++) {
ll p;
cin >> p >> region[i];
v[p].push_back(i);
v[i].push_back(p);
vertices[region[i]].push_back(i);
cati[region[i]]++;
}
ll 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(ll 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(ll j = 1; j <= n; j++) {
preorder[j] += preorder[j - 1];
}
for(ll j = 1; j <= sc; j++) {
for(auto x : vertices[j])
precalc[j][bigIdx[i]] += (preorder[timp[x].second] - preorder[timp[x].first - 1]);
}
for(ll j = 1; j <= n; j++)
preorder[j] = 0;
}
while(Q--) {
ll 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
ll i = 0;
ll j = 0;
ll deschise = 0;
vf = 0;
ll 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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 17096 KB | Output is correct |
| 2 | Correct | 10 ms | 17128 KB | Output is correct |
| 3 | Correct | 12 ms | 17224 KB | Output is correct |
| 4 | Correct | 15 ms | 17352 KB | Output is correct |
| 5 | Correct | 18 ms | 17480 KB | Output is correct |
| 6 | Correct | 26 ms | 18504 KB | Output is correct |
| 7 | Correct | 35 ms | 18012 KB | Output is correct |
| 8 | Correct | 38 ms | 18504 KB | Output is correct |
| 9 | Correct | 64 ms | 19656 KB | Output is correct |
| 10 | Correct | 70 ms | 20448 KB | Output is correct |
| 11 | Correct | 119 ms | 20284 KB | Output is correct |
| 12 | Correct | 182 ms | 22248 KB | Output is correct |
| 13 | Correct | 195 ms | 21952 KB | Output is correct |
| 14 | Correct | 209 ms | 22068 KB | Output is correct |
| 15 | Correct | 297 ms | 26904 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 172 ms | 57776 KB | Execution killed with signal 11 |
| 2 | Runtime error | 177 ms | 58064 KB | Execution killed with signal 11 |
| 3 | Runtime error | 187 ms | 64788 KB | Execution killed with signal 11 |
| 4 | Correct | 492 ms | 40956 KB | Output is correct |
| 5 | Correct | 602 ms | 48576 KB | Output is correct |
| 6 | Runtime error | 463 ms | 125516 KB | Execution killed with signal 11 |
| 7 | Runtime error | 655 ms | 131072 KB | Execution killed with signal 11 |
| 8 | Runtime error | 902 ms | 131072 KB | Execution killed with signal 11 |
| 9 | Runtime error | 1185 ms | 131076 KB | Execution killed with signal 9 |
| 10 | Runtime error | 175 ms | 131076 KB | Execution killed with signal 9 |
| 11 | Runtime error | 211 ms | 131076 KB | Execution killed with signal 9 |
| 12 | Runtime error | 1573 ms | 131076 KB | Execution killed with signal 9 |
| 13 | Runtime error | 1523 ms | 131076 KB | Execution killed with signal 9 |
| 14 | Runtime error | 518 ms | 131076 KB | Execution killed with signal 9 |
| 15 | Runtime error | 181 ms | 131076 KB | Execution killed with signal 9 |
| 16 | Runtime error | 175 ms | 131076 KB | Execution killed with signal 9 |
| 17 | Runtime error | 417 ms | 131076 KB | Execution killed with signal 9 |