oj.uz

Submission #655318

# Submission time Handle Problem Language Result Execution time Memory
655318 2022-11-03T20:06:42 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 86304 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=240000+7;
int n;
int k;
vector<pair<int, int>> gg[N];
vector<pair<int,int>> q2[N];
vector<int> q1[N];

const int K = 20;
int p[N];
int pskip[K][N];
int dep[N];
int euler_tour[2 * N];
int tour_sz;
int first_time_on_tour[N];
int last_time_on_tour[N];
int lg2[2 * N];
int idup[N];
//vector<int> g[N];
pair<int, int> tab_lca[2 * N][K];

void dfs_lca(int a, int par = 0)
{
    p[a] = par;
    euler_tour[++tour_sz] = a;
    first_time_on_tour[a] = last_time_on_tour[a] = tour_sz;
    for (auto &it : gg[a])
    {
        int b=it.first;
        int i=it.second;

        if (b==par){
                continue;
        }
        idup[b]=i;
        dep[b] = 1 + dep[a];
        dfs_lca(b, a);
        euler_tour[++tour_sz] = a;
        last_time_on_tour[a] = tour_sz;
    }
}

void lcaTM()
{
    dfs_lca(1);
    for (int i = 2; i <= tour_sz; i++)
    {
        lg2[i] = 1 + lg2[i / 2];
    }
    for (int i = 1; i <= tour_sz; i++)
    {
        tab_lca[i][0] = {dep[euler_tour[i]], euler_tour[i]};
    }
    for (int k = 1; (1 << k) <= tour_sz; k++)
    {
        for (int i = 1; i + (1 << k) - 1 <= tour_sz; i++)
        {
            tab_lca[i][k] = min(tab_lca[i][k - 1], tab_lca[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int lca(int a, int b)
{
    if (first_time_on_tour[a] > last_time_on_tour[b])
    {
        swap(a, b);
    }
    a = first_time_on_tour[a];
    b = last_time_on_tour[b];
    int k = lg2[b - a + 1];
    return min(tab_lca[a][k], tab_lca[b - (1 << k) + 1][k]).second;
}

int goup(int a,int cnt){
        assert(cnt>=0);
        for(int i=0;i<K;i++){
                if(cnt&(1<<i)){
                        a=pskip[i][a];
                }
        }
        return a;
}

int sol[N];
int tp[N];
int inc[N];
int dcr[N];

void dfs2(int a){
        inc[a]=max(inc[a],1);
        dcr[a]=max(dcr[a],1);
        for (auto &it:gg[a]){
                int b=it.first;
                if(b==p[a]){
                        continue;
                }
                if(idup[a]<idup[b]){
                        inc[b]=1+inc[a];
                }else{
                        dcr[b]=1+dcr[a];
                }
                dfs2(b);
        }
}

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

    ///    freopen("___input___.txt","r",stdin);

        cin>>n>>k;

        for(int i=1;i<=n+k-1;i++){
                string s;
                cin>>s;
                assert(s=="S"||s=="Q"||s=="C");
                if(s=="S"){
                        int a,b;
                        cin>>a>>b;
                        ///g[a].push_back(b);
                        ///g[b].push_back(a);
                        gg[a].push_back({b, i});
                        gg[b].push_back({a, i});
                        sol[i]=-1;
                }
                if(s=="Q"){
                        int a,b;
                        cin>>a>>b;
                        if(a==b){
                                tp[i]=1;
                                sol[i]=1;
                        }else{
                                q2[a].push_back({b, i});
                                tp[i]=1;
                                sol[i]=-2;
                        }
                }
                if(s=="C"){
                        int a;
                        cin>>a;
                        q1[a].push_back(i);
                        sol[i]=-3;
                }
        }

        lcaTM();
        dfs2(1);
        /// solve q1 for the general case

        for (int i=1;i<=n;i++){
                pskip[0][i]=p[i];
        }
        for (int k=1;k<K;k++){
                for (int i=1;i<=n;i++){
                        pskip[k][i]=pskip[k-1][pskip[k-1][i]];
                }
        }

        for (int a=1;a<=n;a++){
                for (auto &it:q2[a]){
                        int b=it.first,i=it.second;
                        /**

                        **/
                        /// drumul de la b la a e crescator?
                        vector<int> guys_x,guys_y;
                        int x=a,y=b,z;
                        swap(x,y);
                        z=lca(x,y);
                        int last=-1;
                        if(y!=z){
                                last=idup[y];
                        }else{
                               // cout<<"ici\n";
                                assert(x!=z);
                                assert(dep[x]-dep[z]-1>=0);
                             //   cout<<x << " : "<<dep[x]-dep[z]-1<<"\n";
                                int vlx=goup(x,dep[x]-dep[z]-1);
                                assert(p[vlx]==z);
                                last=idup[vlx];
                        }
                        bool ok2=1;
                        ok2&=(inc[x]>=dep[z]-dep[x]);
                        ok2&=(dcr[y]>=dep[z]-dep[y]);
                        while (x!=z){
                                guys_x.push_back(idup[x]);
                                x=p[x];
                        }
                        while(y!=z){
                                guys_y.push_back(idup[y]);
                                y=p[y];
                        }

                        bool okx=1,oky=1;
                        for (int it=1;it<(int)guys_x.size();it++) {
                                okx&=(guys_x[it-1]<guys_x[it]);
                        }
                        for (int it=1;it<(int)guys_y.size();it++) {
                                oky&=(guys_y[it-1]>guys_y[it]);
                        }

                        vector<int> guys=guys_x;
                        reverse(guys_y.begin(),guys_y.end());
                        for (auto &V:guys_y){
                                guys.push_back(V);
                        }
                        bool ok=1;
                       /* cout<< " ---> ";
                        for (auto &it : guys){
                                cout<<it<<" ";
                        }
                        cout<<"\n";*/
                        assert(!guys.empty());
                        assert(guys.back()==last);
                        for (int it=1;it<(int)guys.size();it++){
                                ok&=(guys[it-1]<guys[it]);
                        }
                        bool ok3=okx&oky;
                        if(!guys_x.empty()&&!guys_y.empty()){
                                /// guys_x, guys_y
                                ok3&=(guys_x.back()<=guys_y[0]);
                        }
                        assert(ok3==ok);
                       /// cout<<" : " <<ok<<" "<<ok2<<"\n";
                        ///assert(ok==ok2);
                        ok&=(guys.back()<i);
                        sol[i]=ok;
                }
        }


        for (int i=1;i<=n+k-1;i++){
                if(tp[i]==1){
                        assert(sol[i]==0||sol[i]==1);
                        if(sol[i]==1){
                                cout<<"yes\n";
                        }else{
                                cout<<"no\n";
                        }
                }
        }

        return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 20260 KB Output is correct
2 Correct 94 ms 22288 KB Output is correct
3 Correct 60 ms 21964 KB Output is correct
4 Correct 585 ms 22316 KB Output is correct
5 Correct 863 ms 22496 KB Output is correct
6 Correct 61 ms 22236 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 20260 KB Output is correct
2 Correct 94 ms 22288 KB Output is correct
3 Correct 60 ms 21964 KB Output is correct
4 Correct 585 ms 22316 KB Output is correct
5 Correct 863 ms 22496 KB Output is correct
6 Correct 61 ms 22236 KB Output is correct
7 Incorrect 60 ms 20032 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 48 ms 20316 KB Output is correct
2 Correct 228 ms 78712 KB Output is correct
3 Correct 233 ms 78712 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 20316 KB Output is correct
2 Correct 228 ms 78712 KB Output is correct
3 Correct 233 ms 78712 KB Output is correct
4 Incorrect 49 ms 20044 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20340 KB Output is correct
2 Correct 237 ms 85496 KB Output is correct
3 Correct 241 ms 85608 KB Output is correct
4 Execution timed out 3569 ms 85948 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20340 KB Output is correct
2 Correct 237 ms 85496 KB Output is correct
3 Correct 241 ms 85608 KB Output is correct
4 Execution timed out 3569 ms 85948 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 20260 KB Output is correct
2 Correct 243 ms 78860 KB Output is correct
3 Correct 211 ms 78072 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 20260 KB Output is correct
2 Correct 243 ms 78860 KB Output is correct
3 Correct 211 ms 78072 KB Output is correct
4 Incorrect 62 ms 20012 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 20300 KB Output is correct
2 Correct 245 ms 85536 KB Output is correct
3 Correct 240 ms 85704 KB Output is correct
4 Execution timed out 3560 ms 86072 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 20300 KB Output is correct
2 Correct 245 ms 85536 KB Output is correct
3 Correct 240 ms 85704 KB Output is correct
4 Execution timed out 3560 ms 86072 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 20340 KB Output is correct
2 Correct 96 ms 22168 KB Output is correct
3 Correct 70 ms 21948 KB Output is correct
4 Correct 659 ms 22312 KB Output is correct
5 Correct 861 ms 22492 KB Output is correct
6 Correct 60 ms 22220 KB Output is correct
7 Correct 47 ms 20304 KB Output is correct
8 Correct 220 ms 78808 KB Output is correct
9 Correct 219 ms 78692 KB Output is correct
10 Correct 74 ms 20252 KB Output is correct
11 Correct 225 ms 85556 KB Output is correct
12 Correct 217 ms 85592 KB Output is correct
13 Execution timed out 3571 ms 86304 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 20340 KB Output is correct
2 Correct 96 ms 22168 KB Output is correct
3 Correct 70 ms 21948 KB Output is correct
4 Correct 659 ms 22312 KB Output is correct
5 Correct 861 ms 22492 KB Output is correct
6 Correct 60 ms 22220 KB Output is correct
7 Correct 47 ms 20304 KB Output is correct
8 Correct 220 ms 78808 KB Output is correct
9 Correct 219 ms 78692 KB Output is correct
10 Correct 74 ms 20252 KB Output is correct
11 Correct 225 ms 85556 KB Output is correct
12 Correct 217 ms 85592 KB Output is correct
13 Execution timed out 3571 ms 86304 KB Time limit exceeded
14 Halted 0 ms 0 KB -