oj.uz

Submission #1065691

# Submission time Handle Problem Language Result Execution time Memory
1065691 2024-08-19T10:59:12 Z mispertion Inside information (BOI21_servers) C++17
50 / 100
 197 ms 68692 KB 
#include <bits/stdc++.h>

using namespace std;
#pragma GCC optimize("Ofast")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 3e5 + 10;
const int M = 1e5 + 10;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = 1e16;
const int P = 2;

int mult(int a, int b){
    return a * 1LL * b % mod;
}

int sum(int a, int b){
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}

int binpow(int a, int n){
    if (n == 0)
        return 1;
    if (n % 2 == 1){
        return mult(binpow(a, n - 1), a);
    }
    else{
        auto b = binpow(a, n / 2);
        return mult(b, b);
    }
}

const int K = 21;

int n, q, up[N][K], tin[N], tout[N], tick, d[N], edg[N];
vector<int> g[N];
pair<char, pii> qs[N];

struct dsu{
    int p[N], sz[N];
    pii mnd[N];

    dsu(int n){
        for(int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
            mnd[i] = {d[i], i};
        }
    }

    int getp(int v){
        if(p[v] == v)
            return v;
        return p[v] = getp(p[v]);
    }

    void uni(int a, int b){
        a = getp(a);
        b = getp(b);
        if(a == b)
            return;
        if(sz[a] > sz[b])
            swap(a, b);
        p[a] = b;
        sz[b] += sz[a];
        mnd[b] = min(mnd[b], mnd[a]);
    }
};

void dfs(int v, int p){
    tin[v] = ++tick;
    up[v][0] = p;
    for(int k = 1; k < K; k++)
        up[v][k] = up[up[v][k - 1]][k - 1];
    for(auto u : g[v]){
        if(u == p) continue;
        d[u] = d[v] + 1;
        dfs(u, v);
    }
    tout[v] = tick;
}

bool isasc(int p, int v){
    return (tin[p] <= tin[v] && tout[v] <= tout[p]);
}

int prlca(int v, int u){
    for(int k = K - 1; k >= 0; k--){
        if(!isasc(up[v][k], u))
            v = up[v][k];
    }
    return v;
}

void solve(){
    //freopen("in.txt", "r", stdin);
    cin >> n >> q;
    for(int i = 1; i <= n + q - 1; i++){
        char tp;
        cin >> tp;
        int a, b;
        if(tp == 'S'){
            cin >> a >> b;
            g[a].pb(b);
            g[b].pb(a);
        }else if(tp == 'Q'){
            cin >> a >> b;
        }else{
            cin >> a;
        }
        qs[i] = {tp, {a, b}};
    }
    dfs(1, 1);
    dsu inc = dsu(n);
    dsu dec = dsu(n);
    int cur = 0;
    for(int i = 1; i <= n + q - 1; i++){
        if(qs[i].F == 'S'){
            int u = qs[i].S.F, v = qs[i].S.S;
            if(up[v][0] != u)
                swap(u, v);
            edg[v] = ++cur;
            for(auto to : g[v]){
                if(to == u) continue;
                if(edg[to]){
                    inc.uni(v, to);
                }
            }
            if(edg[u])
                dec.uni(v, u);
        }else if(qs[i].F == 'Q'){
            int fr = qs[i].S.S, to = qs[i].S.F;
            if(isasc(fr, to)){
                int v = dec.mnd[dec.getp(to)].S;
                if(isasc(v, fr)){
                    cout << "yes\n";
                    continue;
                }
                if(up[v][0] != fr){
                    cout << "no\n";
                    continue;
                }
                if(edg[v]){
                    cout << "yes\n";
                }else{
                    cout << "no\n";
                }
            }else if(isasc(to, fr)){
                int v = inc.mnd[inc.getp(fr)].S;
                if(isasc(v, to)){
                    cout << "yes\n";
                    continue;
                }
                if(up[v][0] != to){
                    cout << "no\n";
                    continue;
                }
                if(edg[v]){
                    cout << "yes\n";
                }else{
                    cout << "no\n";
                }
            }else{
                int ufr = inc.mnd[inc.getp(fr)].S;
                int uto = dec.mnd[dec.getp(to)].S;
                int lfr = prlca(fr, to);
                int lto = prlca(to, fr);
                if(!isasc(ufr, lfr) || !isasc(uto, lto)){
                    cout << "no\n";
                    continue;
                } 
                if(edg[lfr] && edg[lto] && edg[lfr] < edg[lto]){
                    cout << "yes\n";
                }else{
                    cout << "no\n";
                }
            }
        }else{
            cout << 0 << '\n';
        }
    }
}

signed main(){
    mispertion;
    int t = 1;
    //cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 30404 KB Output is correct
2 Correct 62 ms 31824 KB Output is correct
3 Correct 64 ms 31848 KB Output is correct
4 Correct 59 ms 31828 KB Output is correct
5 Correct 31 ms 31824 KB Output is correct
6 Correct 52 ms 31836 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 30404 KB Output is correct
2 Correct 62 ms 31824 KB Output is correct
3 Correct 64 ms 31848 KB Output is correct
4 Correct 59 ms 31828 KB Output is correct
5 Correct 31 ms 31824 KB Output is correct
6 Correct 52 ms 31836 KB Output is correct
7 Incorrect 42 ms 30292 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 30276 KB Output is correct
2 Correct 123 ms 63172 KB Output is correct
3 Correct 134 ms 63424 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 30276 KB Output is correct
2 Correct 123 ms 63172 KB Output is correct
3 Correct 134 ms 63424 KB Output is correct
4 Incorrect 45 ms 30292 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 30288 KB Output is correct
2 Correct 108 ms 68432 KB Output is correct
3 Correct 104 ms 68432 KB Output is correct
4 Correct 97 ms 68440 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 30288 KB Output is correct
2 Correct 108 ms 68432 KB Output is correct
3 Correct 104 ms 68432 KB Output is correct
4 Correct 97 ms 68440 KB Output is correct
5 Incorrect 28 ms 30300 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 30288 KB Output is correct
2 Correct 123 ms 63572 KB Output is correct
3 Correct 114 ms 64124 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 30288 KB Output is correct
2 Correct 123 ms 63572 KB Output is correct
3 Correct 114 ms 64124 KB Output is correct
4 Incorrect 43 ms 30288 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 30300 KB Output is correct
2 Correct 144 ms 68560 KB Output is correct
3 Correct 122 ms 68496 KB Output is correct
4 Correct 78 ms 68432 KB Output is correct
5 Correct 44 ms 30292 KB Output is correct
6 Correct 107 ms 63728 KB Output is correct
7 Correct 118 ms 64080 KB Output is correct
8 Correct 171 ms 64588 KB Output is correct
9 Correct 136 ms 64596 KB Output is correct
10 Correct 125 ms 67736 KB Output is correct
11 Correct 177 ms 67308 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 30300 KB Output is correct
2 Correct 144 ms 68560 KB Output is correct
3 Correct 122 ms 68496 KB Output is correct
4 Correct 78 ms 68432 KB Output is correct
5 Correct 44 ms 30292 KB Output is correct
6 Correct 107 ms 63728 KB Output is correct
7 Correct 118 ms 64080 KB Output is correct
8 Correct 171 ms 64588 KB Output is correct
9 Correct 136 ms 64596 KB Output is correct
10 Correct 125 ms 67736 KB Output is correct
11 Correct 177 ms 67308 KB Output is correct
12 Incorrect 27 ms 30292 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 30400 KB Output is correct
2 Correct 63 ms 31824 KB Output is correct
3 Correct 52 ms 31900 KB Output is correct
4 Correct 57 ms 31828 KB Output is correct
5 Correct 34 ms 31848 KB Output is correct
6 Correct 65 ms 31956 KB Output is correct
7 Correct 48 ms 30348 KB Output is correct
8 Correct 119 ms 63424 KB Output is correct
9 Correct 110 ms 63176 KB Output is correct
10 Correct 27 ms 30300 KB Output is correct
11 Correct 118 ms 68360 KB Output is correct
12 Correct 133 ms 68692 KB Output is correct
13 Correct 104 ms 68432 KB Output is correct
14 Correct 43 ms 30288 KB Output is correct
15 Correct 104 ms 63588 KB Output is correct
16 Correct 105 ms 64284 KB Output is correct
17 Correct 162 ms 64596 KB Output is correct
18 Correct 164 ms 64596 KB Output is correct
19 Correct 138 ms 67668 KB Output is correct
20 Correct 197 ms 67156 KB Output is correct
21 Correct 124 ms 63812 KB Output is correct
22 Correct 145 ms 63924 KB Output is correct
23 Correct 131 ms 64084 KB Output is correct
24 Correct 129 ms 64136 KB Output is correct
25 Correct 134 ms 64972 KB Output is correct
26 Correct 138 ms 63572 KB Output is correct
27 Correct 102 ms 63572 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 30400 KB Output is correct
2 Correct 63 ms 31824 KB Output is correct
3 Correct 52 ms 31900 KB Output is correct
4 Correct 57 ms 31828 KB Output is correct
5 Correct 34 ms 31848 KB Output is correct
6 Correct 65 ms 31956 KB Output is correct
7 Correct 48 ms 30348 KB Output is correct
8 Correct 119 ms 63424 KB Output is correct
9 Correct 110 ms 63176 KB Output is correct
10 Correct 27 ms 30300 KB Output is correct
11 Correct 118 ms 68360 KB Output is correct
12 Correct 133 ms 68692 KB Output is correct
13 Correct 104 ms 68432 KB Output is correct
14 Correct 43 ms 30288 KB Output is correct
15 Correct 104 ms 63588 KB Output is correct
16 Correct 105 ms 64284 KB Output is correct
17 Correct 162 ms 64596 KB Output is correct
18 Correct 164 ms 64596 KB Output is correct
19 Correct 138 ms 67668 KB Output is correct
20 Correct 197 ms 67156 KB Output is correct
21 Correct 124 ms 63812 KB Output is correct
22 Correct 145 ms 63924 KB Output is correct
23 Correct 131 ms 64084 KB Output is correct
24 Correct 129 ms 64136 KB Output is correct
25 Correct 134 ms 64972 KB Output is correct
26 Correct 138 ms 63572 KB Output is correct
27 Correct 102 ms 63572 KB Output is correct
28 Incorrect 45 ms 30292 KB Extra information in the output file
29 Halted 0 ms 0 KB -