oj.uz

Submission #1026008

# Submission time Handle Problem Language Result Execution time Memory
1026008 2024-07-17T12:30:35 Z happy_node Inside information (BOI21_servers) C++17
0 / 100
 31 ms 18916 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2e5+5;

int N,K;

char tp[MX];
int A[MX], B[MX];

vector<pair<int,int>> adj[MX], Q[MX], C[MX];

bool vis[MX];
int ans[MX], sz[MX], stk[MX];

int getSize(int v, int p) {
        sz[v]=1;
        for(auto [u,w]:adj[v]) {
                if(u==p || vis[u]) continue;
                sz[v]+=getSize(u,v);
        }
        return sz[v];
}

int getCen(int v, int p, int s) {
        for(auto [u,w]:adj[v]) {
                if(u==p || vis[u] || 2*sz[u]<=s) continue;
                return getCen(u,v,s);
        }
        return v;
}

void calc(int v, int p, int prv) {
        for(auto [a,id]:Q[v]) {
                if(stk[a]!=0 && stk[a]<=id) {
                        ans[id]=1;
                }
        }
        for(auto [u,w]:adj[v]) {
                if(u==p) continue;
                if(prv<w) continue;
                calc(u,v,w);
        }
}

void upd(int v, int p, int prv) {
        stk[v]=prv;
        for(auto [u,w]:adj[v]) {
                if(u==p) continue;
                if(prv>w) continue;
                upd(u,v,w);
        }
}

void rem(int v, int p) {
        stk[v]=0;
        for(auto [u,w]:adj[v]) {
                if(u==p) continue;
                rem(u,v);
        }
}

void cdc(int v, int p) {
        int s=getSize(v,v);
        int cen=getCen(v,v,s);

        vis[cen]=1;

        sort(adj[cen].begin(),adj[cen].end(),[&](auto x, auto y) {
                return x.second>y.second;
        });

        stk[cen]=1;

        for(auto [u,w]:adj[cen]) {
                if(vis[u]) continue;
                calc(u,cen,w);
                upd(u,cen,w);
        }

        for(auto [a,id]:Q[cen]) {
                if(stk[a]!=0 && stk[a]<=id) {
                        ans[id]=1;
                }
        }

        stk[cen]=0;

        for(auto [u,w]:adj[cen]) {
                if(vis[u]) continue;
                rem(u,cen);
        }

        for(auto [u,w]:adj[cen]) {
                if(vis[u]) continue;
                cdc(u,cen);
        }
}

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

        cin>>N>>K;

        for(int i=1;i<N+K;i++) {
                cin>>tp[i]>>A[i]>>B[i];
                if(tp[i]=='S') {
                        adj[A[i]].push_back({B[i],i});
                        adj[B[i]].push_back({A[i],i});
                } else if(tp[i]=='Q') {
                        // B -> A path increasing
                        Q[B[i]].push_back({A[i],i});
                } 
        }

        cdc(1,0);

        for(int i=1;i<N+K;i++) {
                if(tp[i]=='S') continue;
                if(ans[i]) cout<<"yes\n";
                else cout<<"no\n";
        }
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 18780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 18780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 18916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 18916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 18776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 18776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 18780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 18780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 18776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 18776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 18776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 18776 KB Output isn't correct
2 Halted 0 ms 0 KB -