답안 #413482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413482 2021-05-28T19:14:51 Z JerryLiu06 Regions (IOI09_regions) C++17
60 / 100
8000 ms 25172 KB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using db = long 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 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)

const int MOD = 1e9 + 7;
const int MXN = 2e5 + 10;
const int MXR = 25010;
const ll INF = 1e18;

const int BLOCK = 450;

int N, R, Q; vi adj[MXN]; int L[MXN]; // L[i] = Region of i

int timer = 1, in[MXN], out[MXN]; vi S[MXR]; // Sorted list of {in, out} for each region

vi large; int up[BLOCK][MXR], down[BLOCK][MXR];

int ind[MXN];

// Preorder Traversal ~ O(N)

void DFS(int X, int P) {
    in[X] = timer++; S[L[X]].pb(X);
    
    EACH(Y, adj[X]) if (Y != P) DFS(Y, X); out[X] = timer - 1;
}
bool isAnc(int A, int B) { return in[A] <= in[B] && out[B] <= out[A]; }

// Get the answer when queried (A, B) ~ O(N)

int genAns(int A, int B) {
    int ans = 0; int L = 0, R = 0; int last = 0; deque<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 (sz(anc) && !isAnc(anc.bk, S[A][L])) anc.pop_back(); anc.pb(S[A][L++]);
        }
        else { while (sz(anc) && !isAnc(anc.bk, S[B][R])) anc.pop_back(); ans += sz(anc); R++; }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> R >> Q >> L[1];

    FOR(i, 2, N + 1) { int A; cin >> A >> L[i]; adj[A].pb(i), adj[i].pb(A); }

    DFS(1, 0); 
    
    int cur = 0; FOR(i, 1, R + 1) if (sz(S[i]) >= BLOCK) large.pb(i), ind[i] = cur++;

    F0R(i, sz(large)) {
        FOR(j, 1, R + 1) { 
            up[i][j] = genAns(large[i], j); 
            down[i][j] = genAns(j, large[i]); 
        }
    }
    F0R(i, Q) {
        int A, B; cin >> A>> B; 
        
        if (sz(S[A]) >= BLOCK) cout << up[ind[A]][B] << endl;
        
        else if (sz(S[B]) >= BLOCK) cout << down[ind[B]][A] << endl;
        
        else cout << genAns(A, B) << endl;
    }
}

Compilation message

regions.cpp: In function 'void DFS(int, int)':
regions.cpp:42:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   42 | #define EACH(a, x) for (auto& a : x)
      |                    ^~~
regions.cpp:64:5: note: in expansion of macro 'EACH'
   64 |     EACH(Y, adj[X]) if (Y != P) DFS(Y, X); out[X] = timer - 1;
      |     ^~~~
regions.cpp:64:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   64 |     EACH(Y, adj[X]) if (Y != P) DFS(Y, X); out[X] = timer - 1;
      |                                            ^~~
regions.cpp: In function 'int genAns(int, int)':
regions.cpp:75:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   75 |             while (sz(anc) && !isAnc(anc.bk, S[A][L])) anc.pop_back(); anc.pb(S[A][L++]);
      |             ^~~~~
regions.cpp:75:72: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   75 |             while (sz(anc) && !isAnc(anc.bk, S[A][L])) anc.pop_back(); anc.pb(S[A][L++]);
      |                                                                        ^~~
regions.cpp:71:40: warning: unused variable 'last' [-Wunused-variable]
   71 |     int ans = 0; int L = 0, R = 0; int last = 0; deque<int> anc;
      |                                        ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5576 KB Output is correct
2 Correct 5 ms 5576 KB Output is correct
3 Correct 5 ms 5576 KB Output is correct
4 Correct 9 ms 5576 KB Output is correct
5 Correct 12 ms 5576 KB Output is correct
6 Correct 23 ms 5576 KB Output is correct
7 Correct 43 ms 5576 KB Output is correct
8 Correct 46 ms 5704 KB Output is correct
9 Correct 63 ms 6088 KB Output is correct
10 Correct 54 ms 6088 KB Output is correct
11 Correct 110 ms 6344 KB Output is correct
12 Correct 92 ms 6740 KB Output is correct
13 Correct 209 ms 6776 KB Output is correct
14 Correct 284 ms 7036 KB Output is correct
15 Correct 379 ms 9416 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1497 ms 10132 KB Output is correct
2 Correct 1569 ms 9848 KB Output is correct
3 Correct 2506 ms 11720 KB Output is correct
4 Correct 324 ms 7244 KB Output is correct
5 Correct 499 ms 8520 KB Output is correct
6 Correct 5760 ms 12432 KB Output is correct
7 Correct 3006 ms 10752 KB Output is correct
8 Execution timed out 8029 ms 20032 KB Time limit exceeded
9 Correct 2661 ms 14212 KB Output is correct
10 Execution timed out 8055 ms 24568 KB Time limit exceeded
11 Correct 3632 ms 16292 KB Output is correct
12 Execution timed out 8031 ms 15424 KB Time limit exceeded
13 Execution timed out 8009 ms 16316 KB Time limit exceeded
14 Execution timed out 8025 ms 16836 KB Time limit exceeded
15 Execution timed out 8048 ms 19436 KB Time limit exceeded
16 Execution timed out 8050 ms 25172 KB Time limit exceeded
17 Execution timed out 8010 ms 24704 KB Time limit exceeded