oj.uz

Submission #1065591

# Submission time Handle Problem Language Result Execution time Memory
1065591 2024-08-19T09:43:43 Z mispertion Inside information (BOI21_servers) C++17
10 / 100
 170 ms 68536 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 = p[a];
        b = p[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(){
    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 40 ms 30292 KB Output is correct
2 Correct 56 ms 31676 KB Output is correct
3 Correct 56 ms 31912 KB Output is correct
4 Correct 84 ms 31824 KB Output is correct
5 Correct 31 ms 32088 KB Output is correct
6 Correct 54 ms 31772 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 30292 KB Output is correct
2 Correct 56 ms 31676 KB Output is correct
3 Correct 56 ms 31912 KB Output is correct
4 Correct 84 ms 31824 KB Output is correct
5 Correct 31 ms 32088 KB Output is correct
6 Correct 54 ms 31772 KB Output is correct
7 Incorrect 40 ms 30288 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 57 ms 30332 KB Output is correct
2 Correct 120 ms 63380 KB Output is correct
3 Correct 170 ms 63388 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 30332 KB Output is correct
2 Correct 120 ms 63380 KB Output is correct
3 Correct 170 ms 63388 KB Output is correct
4 Incorrect 41 ms 30288 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 25 ms 30300 KB Output is correct
2 Correct 106 ms 68436 KB Output is correct
3 Correct 117 ms 68536 KB Output is correct
4 Correct 81 ms 68296 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 30300 KB Output is correct
2 Correct 106 ms 68436 KB Output is correct
3 Correct 117 ms 68536 KB Output is correct
4 Correct 81 ms 68296 KB Output is correct
5 Incorrect 26 ms 30384 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 30288 KB Output is correct
2 Correct 146 ms 63832 KB Output is correct
3 Incorrect 109 ms 64084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 30288 KB Output is correct
2 Correct 146 ms 63832 KB Output is correct
3 Incorrect 109 ms 64084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 30292 KB Output is correct
2 Correct 108 ms 68356 KB Output is correct
3 Correct 115 ms 68432 KB Output is correct
4 Correct 81 ms 68436 KB Output is correct
5 Correct 39 ms 30292 KB Output is correct
6 Correct 137 ms 63676 KB Output is correct
7 Incorrect 109 ms 64272 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 30292 KB Output is correct
2 Correct 108 ms 68356 KB Output is correct
3 Correct 115 ms 68432 KB Output is correct
4 Correct 81 ms 68436 KB Output is correct
5 Correct 39 ms 30292 KB Output is correct
6 Correct 137 ms 63676 KB Output is correct
7 Incorrect 109 ms 64272 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 30152 KB Output is correct
2 Correct 54 ms 31720 KB Output is correct
3 Correct 51 ms 31836 KB Output is correct
4 Correct 56 ms 31828 KB Output is correct
5 Correct 44 ms 31924 KB Output is correct
6 Correct 76 ms 31908 KB Output is correct
7 Correct 43 ms 30400 KB Output is correct
8 Correct 112 ms 63168 KB Output is correct
9 Correct 112 ms 63172 KB Output is correct
10 Correct 30 ms 30292 KB Output is correct
11 Correct 103 ms 68364 KB Output is correct
12 Correct 111 ms 68368 KB Output is correct
13 Correct 79 ms 68464 KB Output is correct
14 Correct 40 ms 30292 KB Output is correct
15 Correct 107 ms 63572 KB Output is correct
16 Incorrect 107 ms 64084 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 30152 KB Output is correct
2 Correct 54 ms 31720 KB Output is correct
3 Correct 51 ms 31836 KB Output is correct
4 Correct 56 ms 31828 KB Output is correct
5 Correct 44 ms 31924 KB Output is correct
6 Correct 76 ms 31908 KB Output is correct
7 Correct 43 ms 30400 KB Output is correct
8 Correct 112 ms 63168 KB Output is correct
9 Correct 112 ms 63172 KB Output is correct
10 Correct 30 ms 30292 KB Output is correct
11 Correct 103 ms 68364 KB Output is correct
12 Correct 111 ms 68368 KB Output is correct
13 Correct 79 ms 68464 KB Output is correct
14 Correct 40 ms 30292 KB Output is correct
15 Correct 107 ms 63572 KB Output is correct
16 Incorrect 107 ms 64084 KB Output isn't correct
17 Halted 0 ms 0 KB -