oj.uz

답안 #1040524

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

vector<int> g[500005];
vector<int> rg[500005];
int par[500005][20];
int dep[500005];
int ddep[500005];
int t;
void dfs(int u, int p = 0, int d = 0){
    ddep[u] = d;
    par[u][0] = p;
    dep[u] = dep[p]+1;
    for(int i = 1; i < 20; i++) par[u][i] = par[par[u][i-1]][i-1];
    for(int v : g[u]){
        if(v == p) continue;
        dfs(v, u, d+1);
    }
    for(int v : rg[u]){
        if(v == p) continue;
        dfs(v, u, d-1);
    }
}
int lca(int u, int v){
    if(dep[u] > dep[v]) swap(u, v);
    for(int i = 19; i >= 0; i--){
        if(dep[u] <= dep[par[v][i]]) v = par[v][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
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);
    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 125 ms 31432 KB Output is correct
2 Correct 148 ms 34008 KB Output is correct
3 Correct 131 ms 34304 KB Output is correct
4 Correct 138 ms 34168 KB Output is correct
5 Correct 134 ms 34560 KB Output is correct
6 Correct 143 ms 34560 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 31432 KB Output is correct
2 Correct 148 ms 34008 KB Output is correct
3 Correct 131 ms 34304 KB Output is correct
4 Correct 138 ms 34168 KB Output is correct
5 Correct 134 ms 34560 KB Output is correct
6 Correct 143 ms 34560 KB Output is correct
7 Correct 244 ms 31432 KB Output is correct
8 Correct 788 ms 36312 KB Output is correct
9 Correct 758 ms 36356 KB Output is correct
10 Correct 804 ms 36064 KB Output is correct
11 Correct 987 ms 36356 KB Output is correct
12 Correct 853 ms 36356 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 31428 KB Output is correct
2 Correct 252 ms 81384 KB Output is correct
3 Correct 224 ms 80640 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 31428 KB Output is correct
2 Correct 252 ms 81384 KB Output is correct
3 Correct 224 ms 80640 KB Output is correct
4 Correct 228 ms 31428 KB Output is correct
5 Execution timed out 3526 ms 77564 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 31428 KB Output is correct
2 Correct 254 ms 79652 KB Output is correct
3 Correct 254 ms 79100 KB Output is correct
4 Correct 215 ms 79376 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 31428 KB Output is correct
2 Correct 254 ms 79652 KB Output is correct
3 Correct 254 ms 79100 KB Output is correct
4 Correct 215 ms 79376 KB Output is correct
5 Correct 231 ms 31380 KB Output is correct
6 Execution timed out 3571 ms 76152 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 31592 KB Output is correct
2 Correct 192 ms 69636 KB Output is correct
3 Correct 227 ms 69896 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 31592 KB Output is correct
2 Correct 192 ms 69636 KB Output is correct
3 Correct 227 ms 69896 KB Output is correct
4 Correct 245 ms 31592 KB Output is correct
5 Execution timed out 3569 ms 67552 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 31544 KB Output is correct
2 Correct 254 ms 78964 KB Output is correct
3 Correct 256 ms 78468 KB Output is correct
4 Correct 203 ms 80948 KB Output is correct
5 Correct 124 ms 31440 KB Output is correct
6 Correct 199 ms 70652 KB Output is correct
7 Correct 227 ms 69384 KB Output is correct
8 Correct 255 ms 70684 KB Output is correct
9 Correct 265 ms 71260 KB Output is correct
10 Correct 234 ms 75008 KB Output is correct
11 Correct 239 ms 74244 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 31544 KB Output is correct
2 Correct 254 ms 78964 KB Output is correct
3 Correct 256 ms 78468 KB Output is correct
4 Correct 203 ms 80948 KB Output is correct
5 Correct 124 ms 31440 KB Output is correct
6 Correct 199 ms 70652 KB Output is correct
7 Correct 227 ms 69384 KB Output is correct
8 Correct 255 ms 70684 KB Output is correct
9 Correct 265 ms 71260 KB Output is correct
10 Correct 234 ms 75008 KB Output is correct
11 Correct 239 ms 74244 KB Output is correct
12 Correct 241 ms 31592 KB Output is correct
13 Execution timed out 3539 ms 76296 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 31604 KB Output is correct
2 Correct 134 ms 34032 KB Output is correct
3 Correct 140 ms 34364 KB Output is correct
4 Correct 145 ms 34116 KB Output is correct
5 Correct 141 ms 34308 KB Output is correct
6 Correct 137 ms 34564 KB Output is correct
7 Correct 123 ms 31500 KB Output is correct
8 Correct 230 ms 81276 KB Output is correct
9 Correct 222 ms 79876 KB Output is correct
10 Correct 127 ms 31564 KB Output is correct
11 Correct 256 ms 78460 KB Output is correct
12 Correct 239 ms 78596 KB Output is correct
13 Correct 207 ms 81152 KB Output is correct
14 Correct 127 ms 31584 KB Output is correct
15 Correct 191 ms 70604 KB Output is correct
16 Correct 229 ms 70400 KB Output is correct
17 Correct 240 ms 70400 KB Output is correct
18 Correct 252 ms 69636 KB Output is correct
19 Correct 224 ms 73984 KB Output is correct
20 Correct 230 ms 72960 KB Output is correct
21 Correct 252 ms 73632 KB Output is correct
22 Correct 239 ms 73960 KB Output is correct
23 Correct 266 ms 71428 KB Output is correct
24 Correct 300 ms 70660 KB Output is correct
25 Correct 255 ms 76288 KB Output is correct
26 Correct 223 ms 71424 KB Output is correct
27 Correct 225 ms 70892 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 31604 KB Output is correct
2 Correct 134 ms 34032 KB Output is correct
3 Correct 140 ms 34364 KB Output is correct
4 Correct 145 ms 34116 KB Output is correct
5 Correct 141 ms 34308 KB Output is correct
6 Correct 137 ms 34564 KB Output is correct
7 Correct 123 ms 31500 KB Output is correct
8 Correct 230 ms 81276 KB Output is correct
9 Correct 222 ms 79876 KB Output is correct
10 Correct 127 ms 31564 KB Output is correct
11 Correct 256 ms 78460 KB Output is correct
12 Correct 239 ms 78596 KB Output is correct
13 Correct 207 ms 81152 KB Output is correct
14 Correct 127 ms 31584 KB Output is correct
15 Correct 191 ms 70604 KB Output is correct
16 Correct 229 ms 70400 KB Output is correct
17 Correct 240 ms 70400 KB Output is correct
18 Correct 252 ms 69636 KB Output is correct
19 Correct 224 ms 73984 KB Output is correct
20 Correct 230 ms 72960 KB Output is correct
21 Correct 252 ms 73632 KB Output is correct
22 Correct 239 ms 73960 KB Output is correct
23 Correct 266 ms 71428 KB Output is correct
24 Correct 300 ms 70660 KB Output is correct
25 Correct 255 ms 76288 KB Output is correct
26 Correct 223 ms 71424 KB Output is correct
27 Correct 225 ms 70892 KB Output is correct
28 Correct 242 ms 31432 KB Output is correct
29 Correct 772 ms 35804 KB Output is correct
30 Correct 756 ms 36356 KB Output is correct
31 Correct 823 ms 36064 KB Output is correct
32 Correct 970 ms 36340 KB Output is correct
33 Correct 848 ms 36356 KB Output is correct
34 Correct 232 ms 31436 KB Output is correct
35 Execution timed out 3550 ms 77568 KB Time limit exceeded
36 Halted 0 ms 0 KB -