답안 #446895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446895 2021-07-23T17:53:19 Z JerryLiu06 Regions (IOI09_regions) C++17
35 / 100
3505 ms 60992 KB
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert 
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
template<class T> void remDup(vector<T>& v) { sor(v); v.erase(unique(all(v)), v.end()); }
 
const int MOD = 1e9 + 7;
const int MXN = 2e5 + 10;
const int MXR = 25e3 + 10;
const ll INF = 1e18;
 
const int BLOCK = 450; int N, R, Q; int reg[MXN]; vi adj[MXN];
 
int timer = 1; int in[MXN], out[MXN]; vi S[MXR]; // Sorted list of {in, out}
 
vi allLarge; int ind[MXR]; int par[BLOCK][MXR], child[BLOCK][MXR];
 
void DFS(int X) {
    in[X] = timer++; S[reg[X]].pb(X);
 
    EACH(Y, adj[X]) DFS(Y); out[X] = timer - 1;
}
bool isAnc(int A, int B) { return in[A] <= in[B] && out[B] <= out[A]; }
 
// Get answer for (A, B), sz[A] > BLOCK, sz[B] <= BLOCK ~ O(N)
 
void genPar(int X, int large, int cnt) {
    par[ind[large]][reg[X]] += cnt; int nCnt = cnt + (reg[X] == large);
 
    EACH(Y, adj[X]) genPar(Y, large, nCnt);
}
 
// Get answer for (A, B), sz[A] <= BLOCK, sz[B] > BLOCK ~ O(N)
 
int genChild(int X, int large) {
    int sub = (reg[X] == large); EACH(Y, adj[X]) sub += genChild(Y, large);
 
    child[ind[large]][reg[X]] += sub; return sub;
}
 
// Get answer for (A, B), sz[A], sz[B] <= BLOCK ~ O(BLOCK)
 
int getAns(int A, int B) {
    int L = 0, R = 0; int ans = 0; stack<int> anc;
 
    while (L < sz(S[A]) || R < sz(S[B])) {
        if (L < sz(S[A]) && (R == sz(S[B]) || in[S[A][L]] < in[S[B][R]])) {
            while (!anc.empty() && !isAnc(anc.top(), S[A][L])) anc.pop(); anc.push(S[A][L]); L++;
        }
        else { while (!anc.empty() && !isAnc(anc.top(), S[B][R])) anc.pop(); ans += sz(anc); R++; }
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> N >> R >> Q >> reg[1]; FOR(i, 2, N + 1) { int A; cin >> A >> reg[i]; adj[A].pb(i); }
 
    DFS(1); int cnt = 0; FOR(i, 1, R + 1) if (sz(S[i]) > BLOCK) allLarge.pb(i), ind[i] = cnt++; 
 
    EACH(i, allLarge) { genPar(1, i, 0); genChild(1, i); }
 
    F0R(i, Q) {
        int A, B; cin >> A >> B;
 
        if (sz(S[A]) <= BLOCK && sz(S[B]) <= BLOCK) { cout << getAns(A, B) << endl; continue; }
 
        if (sz(S[A]) > BLOCK) cout << par[ind[A]][B] << endl; else cout << child[A][ind[B]] << endl;
    }
}

Compilation message

regions.cpp: In function 'void DFS(int)':
regions.cpp:45:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   45 | #define EACH(a, x) for (auto& a : x)
      |                    ^~~
regions.cpp:69:5: note: in expansion of macro 'EACH'
   69 |     EACH(Y, adj[X]) DFS(Y); out[X] = timer - 1;
      |     ^~~~
regions.cpp:69:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |     EACH(Y, adj[X]) DFS(Y); out[X] = timer - 1;
      |                             ^~~
regions.cpp: In function 'int getAns(int, int)':
regions.cpp:96:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   96 |             while (!anc.empty() && !isAnc(anc.top(), S[A][L])) anc.pop(); anc.push(S[A][L]); L++;
      |             ^~~~~
regions.cpp:96:75: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   96 |             while (!anc.empty() && !isAnc(anc.top(), S[A][L])) anc.pop(); anc.push(S[A][L]); L++;
      |                                                                           ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5576 KB Output is correct
2 Correct 4 ms 5576 KB Output is correct
3 Correct 6 ms 5532 KB Output is correct
4 Correct 9 ms 5576 KB Output is correct
5 Correct 7 ms 5576 KB Output is correct
6 Correct 28 ms 5704 KB Output is correct
7 Correct 40 ms 5576 KB Output is correct
8 Correct 43 ms 5704 KB Output is correct
9 Correct 37 ms 6088 KB Output is correct
10 Correct 110 ms 6088 KB Output is correct
11 Correct 138 ms 6344 KB Output is correct
12 Correct 124 ms 6748 KB Output is correct
13 Correct 128 ms 6472 KB Output is correct
14 Correct 255 ms 6984 KB Output is correct
15 Correct 322 ms 9416 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1412 ms 10276 KB Output isn't correct
2 Incorrect 1181 ms 8868 KB Output isn't correct
3 Incorrect 2566 ms 12324 KB Output isn't correct
4 Correct 246 ms 7028 KB Output is correct
5 Correct 356 ms 8648 KB Output is correct
6 Runtime error 213 ms 24240 KB Execution killed with signal 11
7 Runtime error 96 ms 20544 KB Execution killed with signal 11
8 Runtime error 384 ms 47580 KB Execution killed with signal 11
9 Correct 2261 ms 13760 KB Output is correct
10 Runtime error 436 ms 60992 KB Execution killed with signal 11
11 Correct 3505 ms 13332 KB Output is correct
12 Runtime error 183 ms 30944 KB Execution killed with signal 11
13 Runtime error 136 ms 31888 KB Execution killed with signal 11
14 Runtime error 799 ms 37740 KB Execution killed with signal 11
15 Runtime error 131 ms 41616 KB Execution killed with signal 11
16 Runtime error 128 ms 56376 KB Execution killed with signal 11
17 Runtime error 282 ms 60220 KB Execution killed with signal 11