oj.uz

답안 #1040575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1040575 2024-08-01T07:35:20 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 236604 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

vector<int> g[500005];
vector<int> rg[500005];
int st[500005];
int dep[500005];
int ddep[500005];
int t;
int ett[1000005];
int rev[1000005];
void dfs(int u, int p = 0, int d = 0){
    t++;
    ddep[u] = d;
    ett[t] = dep[u] = dep[p]+1;
    st[u] = t;
    rev[t] = u;
    for(int v : g[u]){
        if(v == p) continue;
        dfs(v, u, d+1);
        t++;
        ett[t] = dep[u];
        rev[t] = u;
    }
    for(int v : rg[u]){
        if(v == p) continue;
        dfs(v, u, d-1);
        t++;
        ett[t] = dep[u];
        rev[t] = u;
    }
}
pair<int, int> sparse[21][1048576];
void build(){
    for(int i = 0; i < 1000005; i++) sparse[0][i] = {ett[i], rev[i]};
    for(int i = 1; i < 21; i++){
        for(int j = 0; j + (1 << i) < 1048576; j++){
            sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j+(1<<(i-1))]);
        }
    }
}
inline pair<int,int> rmq(const int& l, const int& r){
    int d = r-l+1;
    int lg = 31 - __builtin_clz(d);
    return min(sparse[lg][l], sparse[lg][r-(1<<lg)+1]);
}
inline int lca(const int& u, const int& v){
    if(st[u] > st[v]) return rmq(st[v], st[u]).second;
    else return rmq(st[u], st[v]).second;
}
inline bool search(const int& a, const int& d){
    int l = lca(a, d);
    int dist = dep[a] + dep[d] - 2*dep[l];
    int ddist = ddep[d] - ddep[a];
    return dist == ddist;
}
gp_hash_table<int, int> buffer;
const int THRESH = 1500;
int qs[500005];
int evp[500005];
int update(int u, int p = 0, int d = 0){
    for(int v : rg[u]){
        if(v == p) continue;
        d += update(v, u, 0);
    }
    d += evp[u];
    qs[u] += d;
    for(int v : g[u]){
        if(v == p) continue;
        update(v, u, d);
    }
    return d;
}
int count(int d){
    if(buffer.size() >= THRESH){
        for(auto p : buffer) evp[p.first] += p.second;
        update(1);
        for(auto p : buffer) evp[p.first] -= p.second;
        buffer.clear();
    }
    int ret = qs[d];
    for(auto p : buffer){
        if(search(p.first, d)){
            ret += p.second;
        }
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    k += n-1;
    vector<tuple<int,int,int>> cmds;
    vector<int> ids(n+1);
    for(int i = 1; i <= n; i++){
        ids[i] = i;
    }
    int last = n;
    for(int i = 0; i < k; i++){
        string cmd;
        cin >> cmd;
        int a, b, d;
        switch(cmd[0]){
            case 'S':
                cin >> a >> b;
                last++;
                g[last].push_back(ids[a]);
                rg[ids[a]].push_back(last);
                g[last].push_back(ids[b]);
                rg[ids[b]].push_back(last);
                ids[a] = ids[b] = last;
                cmds.push_back({0, a, b});
                break;
            case 'Q':
                cin >> a >> d;
                cmds.push_back({1, a, d});
                break;
            case 'C':
                cin >> d;
                cmds.push_back({2, d, 0});
                break;
        }
    }
    dfs(1);
    build();
    for(int i = 1; i <= n; i++){
        ids[i] = i;
        qs[i]++;
    }
    last = n;
    for(int i = 0; i < k; i++){
        int a, b, d;
        switch(get<0>(cmds[i])){
            case 0:
                a = get<1>(cmds[i]);
                b = get<2>(cmds[i]);
                buffer[ids[a]]--;
                buffer[ids[b]]--;
                last++;
                ids[a] = ids[b] = last;
                buffer[last] += 2;
                break;
            case 1:
                a = get<1>(cmds[i]);
                d = get<2>(cmds[i]);
                if(search(ids[a], d)) cout << "yes\n";
                else cout << "no\n";
                break;
            case 2:
                d = get<1>(cmds[i]);
                cout << count(d) << "\n";
                break;
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 197064 KB Output is correct
2 Correct 63 ms 197848 KB Output is correct
3 Correct 58 ms 198080 KB Output is correct
4 Correct 59 ms 198020 KB Output is correct
5 Correct 63 ms 198144 KB Output is correct
6 Correct 60 ms 198360 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 197064 KB Output is correct
2 Correct 63 ms 197848 KB Output is correct
3 Correct 58 ms 198080 KB Output is correct
4 Correct 59 ms 198020 KB Output is correct
5 Correct 63 ms 198144 KB Output is correct
6 Correct 60 ms 198360 KB Output is correct
7 Correct 62 ms 197132 KB Output is correct
8 Correct 782 ms 197480 KB Output is correct
9 Correct 531 ms 197944 KB Output is correct
10 Correct 632 ms 197700 KB Output is correct
11 Correct 390 ms 197876 KB Output is correct
12 Correct 229 ms 198152 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 197064 KB Output is correct
2 Correct 353 ms 236520 KB Output is correct
3 Correct 342 ms 236472 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 197064 KB Output is correct
2 Correct 353 ms 236520 KB Output is correct
3 Correct 342 ms 236472 KB Output is correct
4 Correct 58 ms 197064 KB Output is correct
5 Correct 1401 ms 227724 KB Output is correct
6 Correct 1831 ms 227840 KB Output is correct
7 Correct 1661 ms 227788 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 197100 KB Output is correct
2 Correct 224 ms 235140 KB Output is correct
3 Correct 234 ms 235140 KB Output is correct
4 Correct 1100 ms 236464 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 197100 KB Output is correct
2 Correct 224 ms 235140 KB Output is correct
3 Correct 234 ms 235140 KB Output is correct
4 Correct 1100 ms 236464 KB Output is correct
5 Correct 65 ms 197060 KB Output is correct
6 Execution timed out 3533 ms 226296 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 197060 KB Output is correct
2 Correct 145 ms 224712 KB Output is correct
3 Correct 230 ms 224024 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 197060 KB Output is correct
2 Correct 145 ms 224712 KB Output is correct
3 Correct 230 ms 224024 KB Output is correct
4 Correct 55 ms 197064 KB Output is correct
5 Correct 878 ms 215808 KB Output is correct
6 Correct 2162 ms 223956 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 197048 KB Output is correct
2 Correct 199 ms 235136 KB Output is correct
3 Correct 205 ms 235312 KB Output is correct
4 Correct 1135 ms 236604 KB Output is correct
5 Correct 50 ms 197064 KB Output is correct
6 Correct 129 ms 224600 KB Output is correct
7 Correct 237 ms 224064 KB Output is correct
8 Correct 177 ms 224384 KB Output is correct
9 Correct 353 ms 224644 KB Output is correct
10 Correct 156 ms 229224 KB Output is correct
11 Correct 144 ms 228360 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 197048 KB Output is correct
2 Correct 199 ms 235136 KB Output is correct
3 Correct 205 ms 235312 KB Output is correct
4 Correct 1135 ms 236604 KB Output is correct
5 Correct 50 ms 197064 KB Output is correct
6 Correct 129 ms 224600 KB Output is correct
7 Correct 237 ms 224064 KB Output is correct
8 Correct 177 ms 224384 KB Output is correct
9 Correct 353 ms 224644 KB Output is correct
10 Correct 156 ms 229224 KB Output is correct
11 Correct 144 ms 228360 KB Output is correct
12 Correct 54 ms 197064 KB Output is correct
13 Execution timed out 3532 ms 226352 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 197164 KB Output is correct
2 Correct 58 ms 197916 KB Output is correct
3 Correct 58 ms 198100 KB Output is correct
4 Correct 67 ms 198036 KB Output is correct
5 Correct 56 ms 198148 KB Output is correct
6 Correct 55 ms 198152 KB Output is correct
7 Correct 48 ms 197004 KB Output is correct
8 Correct 305 ms 236416 KB Output is correct
9 Correct 301 ms 236420 KB Output is correct
10 Correct 50 ms 197072 KB Output is correct
11 Correct 193 ms 235136 KB Output is correct
12 Correct 208 ms 235132 KB Output is correct
13 Correct 1106 ms 236584 KB Output is correct
14 Correct 56 ms 197064 KB Output is correct
15 Correct 136 ms 224640 KB Output is correct
16 Correct 228 ms 223868 KB Output is correct
17 Correct 182 ms 224424 KB Output is correct
18 Correct 356 ms 224636 KB Output is correct
19 Correct 173 ms 229248 KB Output is correct
20 Correct 149 ms 228492 KB Output is correct
21 Correct 402 ms 229052 KB Output is correct
22 Correct 307 ms 229504 KB Output is correct
23 Correct 360 ms 225916 KB Output is correct
24 Correct 360 ms 225840 KB Output is correct
25 Correct 278 ms 231300 KB Output is correct
26 Correct 200 ms 224800 KB Output is correct
27 Correct 228 ms 224892 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 197164 KB Output is correct
2 Correct 58 ms 197916 KB Output is correct
3 Correct 58 ms 198100 KB Output is correct
4 Correct 67 ms 198036 KB Output is correct
5 Correct 56 ms 198148 KB Output is correct
6 Correct 55 ms 198152 KB Output is correct
7 Correct 48 ms 197004 KB Output is correct
8 Correct 305 ms 236416 KB Output is correct
9 Correct 301 ms 236420 KB Output is correct
10 Correct 50 ms 197072 KB Output is correct
11 Correct 193 ms 235136 KB Output is correct
12 Correct 208 ms 235132 KB Output is correct
13 Correct 1106 ms 236584 KB Output is correct
14 Correct 56 ms 197064 KB Output is correct
15 Correct 136 ms 224640 KB Output is correct
16 Correct 228 ms 223868 KB Output is correct
17 Correct 182 ms 224424 KB Output is correct
18 Correct 356 ms 224636 KB Output is correct
19 Correct 173 ms 229248 KB Output is correct
20 Correct 149 ms 228492 KB Output is correct
21 Correct 402 ms 229052 KB Output is correct
22 Correct 307 ms 229504 KB Output is correct
23 Correct 360 ms 225916 KB Output is correct
24 Correct 360 ms 225840 KB Output is correct
25 Correct 278 ms 231300 KB Output is correct
26 Correct 200 ms 224800 KB Output is correct
27 Correct 228 ms 224892 KB Output is correct
28 Correct 61 ms 197064 KB Output is correct
29 Correct 810 ms 197408 KB Output is correct
30 Correct 508 ms 198008 KB Output is correct
31 Correct 612 ms 197636 KB Output is correct
32 Correct 347 ms 198152 KB Output is correct
33 Correct 226 ms 198152 KB Output is correct
34 Correct 59 ms 196996 KB Output is correct
35 Correct 928 ms 227584 KB Output is correct
36 Correct 1328 ms 227860 KB Output is correct
37 Correct 1281 ms 227580 KB Output is correct
38 Correct 57 ms 197068 KB Output is correct
39 Execution timed out 3552 ms 226124 KB Time limit exceeded
40 Halted 0 ms 0 KB -