oj.uz

답안 #638063

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638063 2022-09-04T13:51:57 Z LeonaRaging Inside information (BOI21_servers) C++14
0 / 100
 73 ms 21064 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;

struct Node {
    int fi, se;
    bool operator < (const Node &other) const {
        return se > other.se;
    }
};

struct seg_tree {
    vector<int> t;
    seg_tree() {
        t.resize(4 * maxn);
    }
    void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) {
        if (l == r) {
            t[v] += val;
            return;
        }
        int m = (l + r) / 2;
        if (pos <= m) update(pos, val, 2 * v, l, m);
        else update(pos, val, 2 * v + 1, m + 1, r);
    }
    int get(int pos, int v = 1, int l = 1, int r = maxn - 1) {
        if (l == r) return t[v];
        int m = (l + r) / 2;
        if (pos <= m) return get(pos, 2 * v, l, m);
        else return get(pos, 2 * v, l, m) + get(pos, 2 * v + 1, m + 1, r);
    }
} IT;

int n, k, leave[maxn], join[maxn], reach[maxn], res[maxn];
set<Node> adj[maxn];
vector<int> query_c[maxn];
set<pair<int,int>> query_q[maxn];
map<int,int> L;
stack<pair<int,int>> rev;

void dfs_in(int u, int p, int pre) {
    auto it = query_q[u].begin();
    while (it != query_q[u].end()) {
        auto idx = L.find(it->fi);
        if (idx == L.end()) {
            it++;
            continue;
        }
        res[it->se] = -1;
        it = query_q[u].erase(it);
    }
    for (auto it : query_c[u])
        res[it] += IT.get(it) + 1;
    for (auto it : adj[u]) {
        int v = it.fi, w = it.se;
        if (w < pre && v != p)
            dfs_in(v, u, w);
    }
}

void dfs_out(int u, int p, int pre) {
    L[u] = pre;
    IT.update(pre, 1);
    rev.push({pre, 1});
    for (auto it : adj[u]) {
        int v = it.fi, w = it.se;
        if (w > pre && v != p)
            dfs_out(v, u, w);
    }
}

void Solve(int u) {
    L.clear();
    L[u] = 0;
    for (auto it : adj[u]) {
        int v = it.fi, w = it.se;
        dfs_in(v, u, w);
        dfs_out(v, u, w);
    }
    auto it = query_q[u].begin();
    while (it != query_q[u].end()) {
        auto idx = L.find(it->fi);
        if (idx == L.end() || idx->se > it->se) {
            it++;
            continue;
        }
        res[it->se] = -1;
        it = query_q[u].erase(it);
    }
    // if (u == 1) clog << IT.get(4);
    for (auto it : query_c[u]) {
        // if (u == 1) clog << it << '\n';
        res[it] += IT.get(it) + 1;
    }
    while (!rev.empty()) {
        int u, i; tie(u, i) = rev.top(); rev.pop();
        IT.update(u, -i);
    }    
}

struct Centroid_Decomposition {
    int sz[maxn];
    int dfs(int u, int p) {
        sz[u] = 1;
        for (auto it : adj[u])
            if (it.fi != p)
                sz[u] += dfs(it.fi, u);
        return sz[u];
    }
    int Centroid(int u, int p, int tot) {
        for (auto it : adj[u])
            if (it.fi != p && sz[it.fi] > tot / 2)
                return Centroid(it.fi, u, tot);
        return u;
    }
    void build(int u) {
        int tot = dfs(u, 0);
        int c = Centroid(u, 0, tot);
        Solve(c);
        vector<Node> del(adj[c].begin(), adj[c].end());
        for (auto it : del) {
            adj[c].erase(it);
            adj[it.fi].erase(adj[it.fi].find({c, it.se}));
            build(it.fi);
        }
    }
} Cen;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n + k - 1; i++)
        res[i] = -3;
    for (int i = 1; i <= n + k - 1; i++) {
        char type; int u; cin >> type >> u;
        if (type == 'S') {
            int v; cin >> v;
            adj[u].insert({v, i});
            adj[v].insert({u, i});
        }
        else if (type == 'Q') {
            int v; cin >> v;
            if (u == v) res[i] = -1;
            else {
                query_q[v].insert({u, i});
                res[i] = -2;
            }
        }
        else {
            query_c[u].pb(i);
            res[i] = 0;
        }
    }
    Cen.build(1);
    for (int i = 1; i <= n + k - 1; i++)
        if (res[i] != -3) {
            if (res[i] >= 0) cout << res[i];
            else cout << (res[i] == -1 ? "yes" : "no");
            cout << '\n';
        }
}

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

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

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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