답안 #413481

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413481 2021-05-28T19:13:49 Z JerryLiu06 Regions (IOI09_regions) C++17
0 / 100
8000 ms 24856 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] << "\n";
        
        else if (sz(S[B]) >= BLOCK) cout << down[ind[B]][A] << "\n";
        
        else cout << genAns(A, B) << "\n";
    }
}

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 Execution timed out 6 ms 5580 KB Time limit exceeded (wall clock)
2 Execution timed out 5 ms 5576 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 5576 KB Time limit exceeded (wall clock)
4 Execution timed out 5 ms 5576 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 5576 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 5576 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 5576 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 5704 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 6088 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 6088 KB Time limit exceeded (wall clock)
11 Execution timed out 9 ms 6344 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 6728 KB Time limit exceeded (wall clock)
13 Execution timed out 12 ms 6728 KB Time limit exceeded (wall clock)
14 Execution timed out 15 ms 7100 KB Time limit exceeded (wall clock)
15 Execution timed out 19 ms 9416 KB Time limit exceeded (wall clock)
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 305 ms 10120 KB Time limit exceeded (wall clock)
2 Execution timed out 350 ms 9792 KB Time limit exceeded (wall clock)
3 Execution timed out 337 ms 11748 KB Time limit exceeded (wall clock)
4 Execution timed out 15 ms 7232 KB Time limit exceeded (wall clock)
5 Execution timed out 19 ms 8640 KB Time limit exceeded (wall clock)
6 Execution timed out 5425 ms 12268 KB Time limit exceeded (wall clock)
7 Execution timed out 1730 ms 10632 KB Time limit exceeded (wall clock)
8 Execution timed out 8068 ms 20048 KB Time limit exceeded
9 Execution timed out 67 ms 14144 KB Time limit exceeded (wall clock)
10 Execution timed out 8025 ms 24340 KB Time limit exceeded
11 Execution timed out 91 ms 16192 KB Time limit exceeded (wall clock)
12 Execution timed out 8016 ms 15564 KB Time limit exceeded
13 Execution timed out 8032 ms 16552 KB Time limit exceeded
14 Execution timed out 8103 ms 16684 KB Time limit exceeded
15 Execution timed out 8060 ms 19376 KB Time limit exceeded
16 Execution timed out 8100 ms 24856 KB Time limit exceeded
17 Execution timed out 8098 ms 24596 KB Time limit exceeded