oj.uz

Submission #655309

# Submission time Handle Problem Language Result Execution time Memory
655309 2022-11-03T19:52:41 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 85364 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;(1<<i)<=cnt;i++){
                if(cnt&(1<<i)){
                        a=pskip[i][a];
                }
        }
        assert(a);
        return a;
}

int sol[N];
int tp[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;
                }
        }
        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]];
                }
        }
        /// solve q1 for the general case
        lcaTM();

        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{
                               // int vlx=goup(x,dep[x]-dep[z]-1);
                              //  assert(p[vlx]==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);
                        }
                        bool ok=1;
                       /* cout<< " ---> ";
                        for (auto &it : guys){
                                cout<<it<<" ";
                        }
                        cout<<"\n";*/
                        assert(!guys.empty());
                        if(last!=-1){
                                assert(guys.back()==last);
                        }
                        for (int it=1;it<(int)guys.size();it++){
                                ok&=(guys[it-1]<guys[it]);
                        }
                        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 70 ms 20240 KB Output is correct
2 Correct 102 ms 22108 KB Output is correct
3 Correct 60 ms 21956 KB Output is correct
4 Correct 584 ms 22260 KB Output is correct
5 Correct 805 ms 22548 KB Output is correct
6 Correct 65 ms 22224 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 20240 KB Output is correct
2 Correct 102 ms 22108 KB Output is correct
3 Correct 60 ms 21956 KB Output is correct
4 Correct 584 ms 22260 KB Output is correct
5 Correct 805 ms 22548 KB Output is correct
6 Correct 65 ms 22224 KB Output is correct
7 Incorrect 78 ms 20012 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 51 ms 20272 KB Output is correct
2 Correct 273 ms 77896 KB Output is correct
3 Correct 256 ms 77768 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 20272 KB Output is correct
2 Correct 273 ms 77896 KB Output is correct
3 Correct 256 ms 77768 KB Output is correct
4 Incorrect 49 ms 20056 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 80 ms 20264 KB Output is correct
2 Correct 237 ms 84632 KB Output is correct
3 Correct 248 ms 84764 KB Output is correct
4 Execution timed out 3580 ms 85364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 20264 KB Output is correct
2 Correct 237 ms 84632 KB Output is correct
3 Correct 248 ms 84764 KB Output is correct
4 Execution timed out 3580 ms 85364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 20264 KB Output is correct
2 Correct 251 ms 77884 KB Output is correct
3 Correct 225 ms 77132 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 20264 KB Output is correct
2 Correct 251 ms 77884 KB Output is correct
3 Correct 225 ms 77132 KB Output is correct
4 Incorrect 78 ms 20104 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 72 ms 20352 KB Output is correct
2 Correct 267 ms 84572 KB Output is correct
3 Correct 239 ms 84660 KB Output is correct
4 Execution timed out 3603 ms 84980 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 20352 KB Output is correct
2 Correct 267 ms 84572 KB Output is correct
3 Correct 239 ms 84660 KB Output is correct
4 Execution timed out 3603 ms 84980 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 20260 KB Output is correct
2 Correct 115 ms 22112 KB Output is correct
3 Correct 69 ms 21980 KB Output is correct
4 Correct 557 ms 22260 KB Output is correct
5 Correct 816 ms 22556 KB Output is correct
6 Correct 63 ms 22144 KB Output is correct
7 Correct 60 ms 20300 KB Output is correct
8 Correct 254 ms 77764 KB Output is correct
9 Correct 281 ms 77756 KB Output is correct
10 Correct 79 ms 20284 KB Output is correct
11 Correct 234 ms 84528 KB Output is correct
12 Correct 217 ms 84740 KB Output is correct
13 Execution timed out 3569 ms 85072 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 20260 KB Output is correct
2 Correct 115 ms 22112 KB Output is correct
3 Correct 69 ms 21980 KB Output is correct
4 Correct 557 ms 22260 KB Output is correct
5 Correct 816 ms 22556 KB Output is correct
6 Correct 63 ms 22144 KB Output is correct
7 Correct 60 ms 20300 KB Output is correct
8 Correct 254 ms 77764 KB Output is correct
9 Correct 281 ms 77756 KB Output is correct
10 Correct 79 ms 20284 KB Output is correct
11 Correct 234 ms 84528 KB Output is correct
12 Correct 217 ms 84740 KB Output is correct
13 Execution timed out 3569 ms 85072 KB Time limit exceeded
14 Halted 0 ms 0 KB -