oj.uz

Submission #655320

# Submission time Handle Problem Language Result Execution time Memory
655320 2022-11-03T20:15:27 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 86272 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);
        }
        ///cout<<"vis "<<a<<" : "<<inc[a]<<" vs "<<dcr[a]<<"\n";
}

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,ok2y=(inc[y]>=dep[y]-dep[z]);
                        ok2&=(dcr[x]>=dep[x]-dep[z]);
                        ///ok2&=(dcr[y]>=dep[z]-dep[y]);
                       /// cout<<" : "<<okx<<" vs "<<inc[x]<<" "<<dep[x]-dep[z]+1<<"\n";
                       int xx=x;
                        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]);
                        }

                       /// cout<<okx<<" : "<<dcr[xx]<<" vs "<<dep[xx]-dep[z]<<"\n";
                        assert(okx==ok2);
                        for (int it=1;it<(int)guys_y.size();it++) {
                                oky&=(guys_y[it-1]>guys_y[it]);
                        }

                        assert(ok2y==oky);
                        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;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:190:28: warning: unused variable 'xx' [-Wunused-variable]
  190 |                        int xx=x;
      |                            ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20476 KB Output is correct
2 Correct 111 ms 22172 KB Output is correct
3 Correct 65 ms 21944 KB Output is correct
4 Correct 582 ms 22312 KB Output is correct
5 Correct 918 ms 22604 KB Output is correct
6 Correct 60 ms 22224 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20476 KB Output is correct
2 Correct 111 ms 22172 KB Output is correct
3 Correct 65 ms 21944 KB Output is correct
4 Correct 582 ms 22312 KB Output is correct
5 Correct 918 ms 22604 KB Output is correct
6 Correct 60 ms 22224 KB Output is correct
7 Incorrect 59 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 49 ms 20328 KB Output is correct
2 Correct 263 ms 78744 KB Output is correct
3 Correct 217 ms 78704 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 20328 KB Output is correct
2 Correct 263 ms 78744 KB Output is correct
3 Correct 217 ms 78704 KB Output is correct
4 Incorrect 47 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 102 ms 20320 KB Output is correct
2 Correct 245 ms 85564 KB Output is correct
3 Correct 222 ms 85676 KB Output is correct
4 Execution timed out 3565 ms 86016 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 20320 KB Output is correct
2 Correct 245 ms 85564 KB Output is correct
3 Correct 222 ms 85676 KB Output is correct
4 Execution timed out 3565 ms 86016 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20368 KB Output is correct
2 Correct 280 ms 78828 KB Output is correct
3 Correct 218 ms 78124 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20368 KB Output is correct
2 Correct 280 ms 78828 KB Output is correct
3 Correct 218 ms 78124 KB Output is correct
4 Incorrect 62 ms 20032 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 87 ms 20300 KB Output is correct
2 Correct 257 ms 85652 KB Output is correct
3 Correct 248 ms 85708 KB Output is correct
4 Execution timed out 3587 ms 86272 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 87 ms 20300 KB Output is correct
2 Correct 257 ms 85652 KB Output is correct
3 Correct 248 ms 85708 KB Output is correct
4 Execution timed out 3587 ms 86272 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 20256 KB Output is correct
2 Correct 96 ms 22168 KB Output is correct
3 Correct 65 ms 22020 KB Output is correct
4 Correct 575 ms 22312 KB Output is correct
5 Correct 920 ms 22484 KB Output is correct
6 Correct 68 ms 22348 KB Output is correct
7 Correct 51 ms 20352 KB Output is correct
8 Correct 217 ms 78736 KB Output is correct
9 Correct 239 ms 78716 KB Output is correct
10 Correct 77 ms 20260 KB Output is correct
11 Correct 240 ms 85576 KB Output is correct
12 Correct 224 ms 85592 KB Output is correct
13 Execution timed out 3595 ms 85956 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 20256 KB Output is correct
2 Correct 96 ms 22168 KB Output is correct
3 Correct 65 ms 22020 KB Output is correct
4 Correct 575 ms 22312 KB Output is correct
5 Correct 920 ms 22484 KB Output is correct
6 Correct 68 ms 22348 KB Output is correct
7 Correct 51 ms 20352 KB Output is correct
8 Correct 217 ms 78736 KB Output is correct
9 Correct 239 ms 78716 KB Output is correct
10 Correct 77 ms 20260 KB Output is correct
11 Correct 240 ms 85576 KB Output is correct
12 Correct 224 ms 85592 KB Output is correct
13 Execution timed out 3595 ms 85956 KB Time limit exceeded
14 Halted 0 ms 0 KB -