oj.uz

답안 #1040540

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1040540 2024-08-01T07:03:49 Z Plurm Inside information (BOI21_servers) C++11
52.5 / 100
 3500 ms 232012 KB 
#include <bits/stdc++.h>
using namespace std;

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))]);
        }
    }
}
pair<int,int> rmq(int l, int r){
    int d = r-l+1;
    int lg = 31 - __builtin_clz(d);
    return min(sparse[lg][l], sparse[lg][r-(1<<lg)+1]);
}
int lca(int u, int v){
    if(st[u] > st[v]) swap(u, v);
    return rmq(st[u], st[v]).second;
}
bool search(int a, 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;
}
vector<pair<int,int>> buffer;
const int THRESH = 200;
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;
        buffer.push_back({i, 1});
    }
    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.push_back({ids[a], -1});
                buffer.push_back({ids[b], -1});
                last++;
                ids[a] = ids[b] = last;
                buffer.push_back({last, 2});
                break;
            case 1:
                a = get<1>(cmds[i]);
                d = get<2>(cmds[i]);
                if(search(ids[a], d)) cout << "yes" << endl;
                else cout << "no" << endl;
                break;
            case 2:
                d = get<1>(cmds[i]);
                cout << count(d) << endl;
                break;
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 190672 KB Output is correct
2 Correct 169 ms 191332 KB Output is correct
3 Correct 178 ms 191488 KB Output is correct
4 Correct 165 ms 191452 KB Output is correct
5 Correct 162 ms 191608 KB Output is correct
6 Correct 162 ms 191744 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 190672 KB Output is correct
2 Correct 169 ms 191332 KB Output is correct
3 Correct 178 ms 191488 KB Output is correct
4 Correct 165 ms 191452 KB Output is correct
5 Correct 162 ms 191608 KB Output is correct
6 Correct 162 ms 191744 KB Output is correct
7 Correct 171 ms 190644 KB Output is correct
8 Correct 218 ms 191080 KB Output is correct
9 Correct 208 ms 191488 KB Output is correct
10 Correct 222 ms 191216 KB Output is correct
11 Correct 228 ms 191492 KB Output is correct
12 Correct 213 ms 191748 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 190668 KB Output is correct
2 Correct 220 ms 226820 KB Output is correct
3 Correct 226 ms 226764 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 190668 KB Output is correct
2 Correct 220 ms 226820 KB Output is correct
3 Correct 226 ms 226764 KB Output is correct
4 Correct 165 ms 190660 KB Output is correct
5 Execution timed out 3558 ms 223856 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 190740 KB Output is correct
2 Correct 262 ms 225612 KB Output is correct
3 Correct 262 ms 225536 KB Output is correct
4 Correct 218 ms 226720 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 190740 KB Output is correct
2 Correct 262 ms 225612 KB Output is correct
3 Correct 262 ms 225536 KB Output is correct
4 Correct 218 ms 226720 KB Output is correct
5 Correct 167 ms 190756 KB Output is correct
6 Execution timed out 3576 ms 222148 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 190744 KB Output is correct
2 Correct 228 ms 215040 KB Output is correct
3 Correct 274 ms 214536 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 190744 KB Output is correct
2 Correct 228 ms 215040 KB Output is correct
3 Correct 274 ms 214536 KB Output is correct
4 Correct 185 ms 190664 KB Output is correct
5 Correct 3336 ms 212224 KB Output is correct
6 Execution timed out 3540 ms 216064 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 191428 KB Output is correct
2 Correct 255 ms 227404 KB Output is correct
3 Correct 250 ms 227328 KB Output is correct
4 Correct 227 ms 228676 KB Output is correct
5 Correct 162 ms 191432 KB Output is correct
6 Correct 222 ms 216820 KB Output is correct
7 Correct 252 ms 216316 KB Output is correct
8 Correct 254 ms 216660 KB Output is correct
9 Correct 245 ms 216764 KB Output is correct
10 Correct 233 ms 221692 KB Output is correct
11 Correct 275 ms 220716 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 191428 KB Output is correct
2 Correct 255 ms 227404 KB Output is correct
3 Correct 250 ms 227328 KB Output is correct
4 Correct 227 ms 228676 KB Output is correct
5 Correct 162 ms 191432 KB Output is correct
6 Correct 222 ms 216820 KB Output is correct
7 Correct 252 ms 216316 KB Output is correct
8 Correct 254 ms 216660 KB Output is correct
9 Correct 245 ms 216764 KB Output is correct
10 Correct 233 ms 221692 KB Output is correct
11 Correct 275 ms 220716 KB Output is correct
12 Correct 163 ms 191432 KB Output is correct
13 Execution timed out 3541 ms 223932 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 191688 KB Output is correct
2 Correct 166 ms 192792 KB Output is correct
3 Correct 160 ms 192780 KB Output is correct
4 Correct 165 ms 192736 KB Output is correct
5 Correct 186 ms 193032 KB Output is correct
6 Correct 160 ms 193028 KB Output is correct
7 Correct 154 ms 191692 KB Output is correct
8 Correct 224 ms 229632 KB Output is correct
9 Correct 221 ms 229632 KB Output is correct
10 Correct 153 ms 191740 KB Output is correct
11 Correct 246 ms 229120 KB Output is correct
12 Correct 246 ms 228820 KB Output is correct
13 Correct 211 ms 230212 KB Output is correct
14 Correct 168 ms 191688 KB Output is correct
15 Correct 239 ms 218372 KB Output is correct
16 Correct 243 ms 217860 KB Output is correct
17 Correct 258 ms 218140 KB Output is correct
18 Correct 261 ms 218368 KB Output is correct
19 Correct 232 ms 222980 KB Output is correct
20 Correct 227 ms 222184 KB Output is correct
21 Correct 235 ms 222720 KB Output is correct
22 Correct 239 ms 223272 KB Output is correct
23 Correct 252 ms 219372 KB Output is correct
24 Correct 246 ms 219648 KB Output is correct
25 Correct 238 ms 225024 KB Output is correct
26 Correct 279 ms 219128 KB Output is correct
27 Correct 283 ms 224768 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 191688 KB Output is correct
2 Correct 166 ms 192792 KB Output is correct
3 Correct 160 ms 192780 KB Output is correct
4 Correct 165 ms 192736 KB Output is correct
5 Correct 186 ms 193032 KB Output is correct
6 Correct 160 ms 193028 KB Output is correct
7 Correct 154 ms 191692 KB Output is correct
8 Correct 224 ms 229632 KB Output is correct
9 Correct 221 ms 229632 KB Output is correct
10 Correct 153 ms 191740 KB Output is correct
11 Correct 246 ms 229120 KB Output is correct
12 Correct 246 ms 228820 KB Output is correct
13 Correct 211 ms 230212 KB Output is correct
14 Correct 168 ms 191688 KB Output is correct
15 Correct 239 ms 218372 KB Output is correct
16 Correct 243 ms 217860 KB Output is correct
17 Correct 258 ms 218140 KB Output is correct
18 Correct 261 ms 218368 KB Output is correct
19 Correct 232 ms 222980 KB Output is correct
20 Correct 227 ms 222184 KB Output is correct
21 Correct 235 ms 222720 KB Output is correct
22 Correct 239 ms 223272 KB Output is correct
23 Correct 252 ms 219372 KB Output is correct
24 Correct 246 ms 219648 KB Output is correct
25 Correct 238 ms 225024 KB Output is correct
26 Correct 279 ms 219128 KB Output is correct
27 Correct 283 ms 224768 KB Output is correct
28 Correct 152 ms 195784 KB Output is correct
29 Correct 204 ms 198620 KB Output is correct
30 Correct 193 ms 198916 KB Output is correct
31 Correct 209 ms 198812 KB Output is correct
32 Correct 214 ms 198912 KB Output is correct
33 Correct 201 ms 199176 KB Output is correct
34 Correct 157 ms 196000 KB Output is correct
35 Execution timed out 3555 ms 232012 KB Time limit exceeded
36 Halted 0 ms 0 KB -