oj.uz

답안 #749118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749118 2023-05-27T11:11:49 Z 이동현(#9963) Inside information (BOI21_servers) C++17
0 / 100
 24 ms 5944 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int NS = 120004;
int tr[NS];

void push(int pos, int val){
    for(int i = pos; i < NS; i += (i & -i)) tr[i] += val;
}

int get(int pos){
    int rv = 0;
    for(int i = pos; i > 0; i -= (i & -i)) rv += tr[i];
    return rv;
}

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

    int n, q;
    cin >> n >> q;
    vector<vector<pair<int, int>>> way(n);
    vector<int> ans(n + q - 1, -1);
    vector<vector<pair<int, int>>> que(n);
    for(int i = 0; i < n + q - 1; ++i){
        char c;
        cin >> c;
        if(c == 'S'){
            int x, y;
            cin >> x >> y;
            --x, --y;
            way[x].push_back({y, i});
            way[y].push_back({x, i});
            ans[i] = -3;
        }
        else if(c == 'Q'){
            int x, y;
            cin >> x >> y;
            --x, --y;
            que[y].push_back({x, i});
        }
        else{
            int x;
            cin >> x;
            --x;
            que[x].push_back({-1, i});
            ans[i] = 0;
        }
    }

    vector<int> chk(n), sz(n), col(n), num(n), noon(n, -1);

    auto dfssz = [&](auto&&self, int x, int pr)->void{
        sz[x] = 1;
        for(auto&nxt:way[x]){
            if(chk[nxt.first] || nxt.first == pr){
                continue;
            }
            self(self, nxt.first, x);
            sz[x] += sz[nxt.first];
        }
    };

    auto getcent = [&](auto&&self, int x, int pr, int asz)->int{
        for(auto&nxt:way[x]){
            if(chk[nxt.first] || nxt.first == pr){
                continue;
            }
            if(sz[nxt.first] * 2 > asz){
                return self(self, nxt.first, x, asz);
            }
        }
        return x;
    };

    auto sol = [&](auto&&self, int ct)->void{
        dfssz(dfssz, ct, -1);
        ct = getcent(getcent, ct, -1, sz[ct]);
        chk[ct] = 1;

        vector<vector<int>> t;
        vector<int> sv;
        vector<pair<int, int>> srt;

        auto mt = [&](auto&&self, int x, int pr, int lst)->void{
            noon[x] = ct;
            col[x] = (int)t.size() - 1;
            num[x] = lst;
            if(lst >= 0 && lst < (int)1e9){
                t.back().push_back(lst);
            }
            for(auto&nxt:way[x]){
                if(nxt.first == pr || chk[nxt.first]){
                    continue;
                }
                self(self, nxt.first, x, (lst < nxt.second ? nxt.second : (int)1e9));
            }
        };

        noon[ct] = ct;
        for(auto&nxt:way[ct]){
            if(chk[nxt.first]){
                continue;
            }
            t.push_back({});
            sv.push_back(nxt.second);
            srt.push_back({nxt.second, nxt.first});
            mt(mt, nxt.first, -1, -1);
            sort(t.back().begin(), t.back().end());
        }

        auto upd = [&](auto&&self, int x, int pr, int lst)->void{
            for(auto&i:que[x]){
                if(ans[i.second] != -1) continue;
                if(i.first == -1){
                    ans[i.second] += get(i.second);
                    if(sv[col[x]] <= i.second) ++ans[i.second];
                }
                else{
                    if(i.first == ct){
                        if(sv[col[x]] <= i.second) ans[i.second] = -5;
                    }
                    else if(noon[i.first] == ct && col[x] != col[i.first]){
                        if(num[i.first] <= i.second && sv[col[i.first]] >= sv[col[x]]) ans[i.second] = -5;
                    }
                }
            }

            for(auto&nxt:way[x]){
                if(chk[nxt.first] || nxt.first == pr || lst < nxt.second){
                    continue;
                }
                self(self, nxt.first, x, nxt.second);
            }
        };

        sort(srt.begin(), srt.end());
        reverse(srt.begin(), srt.end());
        for(auto&nxt:srt){
            upd(upd, nxt.second, -1, nxt.first);
            for(auto&i:t[col[nxt.second]]){
                push(i, 1);
            }
        }

        for(auto&i:que[ct]){
            if(ans[i.second] != -1) continue;
            if(i.first == -1){
                ans[i.second] += get(i.second);
            }
            else if(noon[i.first] == ct){
                if(num[i.first] <= i.second) ans[i.second] = -5;
            }
        }


        for(auto&nxt:srt){
            for(auto&i:t[col[nxt.second]]){
                push(i, -1);
            }
        }

        for(auto&nxt:way[ct]){
            if(chk[nxt.first]){
                continue;
            }
            self(self, nxt.first);
        }
    };

    sol(sol, 0);

    for(auto&i:ans){
        //cout << i << endl;
        if(i != -3){
            if(i == -5) cout << "yes\n";
            else if(i == -1) cout << "no\n";
            else cout << i << '\n';
        }
    }

    return 0;
}

Subtask #1
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 5888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 5888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 5600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 5600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 5800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 5800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 5944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 5944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 5920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 5920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 5908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 5908 KB Output isn't correct
2 Halted 0 ms 0 KB -