oj.uz

Submission #655321

# Submission time Handle Problem Language Result Execution time Memory
655321 2022-11-03T20:17:19 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 86044 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 ok=1;
                        ok&=(inc[y]>=dep[y]-dep[z]);
                        ok&=(dcr[x]>=dep[x]-dep[z]);
                        while (x!=z){
                                guys_x.push_back(idup[x]);
                                x=p[x];
                        }
                        while(y!=z){
                                guys_y.push_back(idup[y]);
                                y=p[y];
                        }
                        vector<int> guys=guys_x;
                        reverse(guys_y.begin(),guys_y.end());
                        for (auto &V:guys_y){
                                guys.push_back(V);
                        }
                        assert(!guys.empty());
                        assert(guys.back()==last);
                        if(!guys_x.empty()&&!guys_y.empty()){
                                ok&=(guys_x.back()<=guys_y[0]);
                        }
                        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 60 ms 20300 KB Output is correct
2 Correct 87 ms 22168 KB Output is correct
3 Correct 59 ms 21928 KB Output is correct
4 Correct 464 ms 22388 KB Output is correct
5 Correct 668 ms 22536 KB Output is correct
6 Correct 59 ms 22264 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 20300 KB Output is correct
2 Correct 87 ms 22168 KB Output is correct
3 Correct 59 ms 21928 KB Output is correct
4 Correct 464 ms 22388 KB Output is correct
5 Correct 668 ms 22536 KB Output is correct
6 Correct 59 ms 22264 KB Output is correct
7 Incorrect 58 ms 20088 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 20376 KB Output is correct
2 Correct 219 ms 78784 KB Output is correct
3 Correct 235 ms 78720 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 20376 KB Output is correct
2 Correct 219 ms 78784 KB Output is correct
3 Correct 235 ms 78720 KB Output is correct
4 Incorrect 45 ms 20076 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 71 ms 20292 KB Output is correct
2 Correct 238 ms 85480 KB Output is correct
3 Correct 222 ms 85672 KB Output is correct
4 Execution timed out 3561 ms 85996 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20292 KB Output is correct
2 Correct 238 ms 85480 KB Output is correct
3 Correct 222 ms 85672 KB Output is correct
4 Execution timed out 3561 ms 85996 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 20256 KB Output is correct
2 Correct 237 ms 78760 KB Output is correct
3 Correct 224 ms 78192 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 20256 KB Output is correct
2 Correct 237 ms 78760 KB Output is correct
3 Correct 224 ms 78192 KB Output is correct
4 Incorrect 60 ms 20068 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 20320 KB Output is correct
2 Correct 220 ms 85532 KB Output is correct
3 Correct 242 ms 85676 KB Output is correct
4 Execution timed out 3575 ms 86044 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 20320 KB Output is correct
2 Correct 220 ms 85532 KB Output is correct
3 Correct 242 ms 85676 KB Output is correct
4 Execution timed out 3575 ms 86044 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 20300 KB Output is correct
2 Correct 89 ms 22168 KB Output is correct
3 Correct 60 ms 22004 KB Output is correct
4 Correct 470 ms 22304 KB Output is correct
5 Correct 680 ms 22492 KB Output is correct
6 Correct 59 ms 22252 KB Output is correct
7 Correct 50 ms 20316 KB Output is correct
8 Correct 214 ms 78672 KB Output is correct
9 Correct 220 ms 78824 KB Output is correct
10 Correct 72 ms 20296 KB Output is correct
11 Correct 226 ms 85564 KB Output is correct
12 Correct 235 ms 85616 KB Output is correct
13 Execution timed out 3548 ms 86020 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 20300 KB Output is correct
2 Correct 89 ms 22168 KB Output is correct
3 Correct 60 ms 22004 KB Output is correct
4 Correct 470 ms 22304 KB Output is correct
5 Correct 680 ms 22492 KB Output is correct
6 Correct 59 ms 22252 KB Output is correct
7 Correct 50 ms 20316 KB Output is correct
8 Correct 214 ms 78672 KB Output is correct
9 Correct 220 ms 78824 KB Output is correct
10 Correct 72 ms 20296 KB Output is correct
11 Correct 226 ms 85564 KB Output is correct
12 Correct 235 ms 85616 KB Output is correct
13 Execution timed out 3548 ms 86020 KB Time limit exceeded
14 Halted 0 ms 0 KB -