oj.uz

Submission #655310

# Submission time Handle Problem Language Result Execution time Memory
655310 2022-11-03T19:52:41 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 85100 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 65 ms 20228 KB Output is correct
2 Correct 107 ms 22152 KB Output is correct
3 Correct 60 ms 21896 KB Output is correct
4 Correct 570 ms 22260 KB Output is correct
5 Correct 848 ms 22444 KB Output is correct
6 Correct 63 ms 22204 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 20228 KB Output is correct
2 Correct 107 ms 22152 KB Output is correct
3 Correct 60 ms 21896 KB Output is correct
4 Correct 570 ms 22260 KB Output is correct
5 Correct 848 ms 22444 KB Output is correct
6 Correct 63 ms 22204 KB Output is correct
7 Incorrect 79 ms 20100 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 50 ms 20304 KB Output is correct
2 Correct 278 ms 77824 KB Output is correct
3 Correct 233 ms 77768 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 20304 KB Output is correct
2 Correct 278 ms 77824 KB Output is correct
3 Correct 233 ms 77768 KB Output is correct
4 Incorrect 55 ms 20116 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 79 ms 20292 KB Output is correct
2 Correct 258 ms 84620 KB Output is correct
3 Correct 254 ms 84760 KB Output is correct
4 Execution timed out 3601 ms 84988 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 20292 KB Output is correct
2 Correct 258 ms 84620 KB Output is correct
3 Correct 254 ms 84760 KB Output is correct
4 Execution timed out 3601 ms 84988 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 20288 KB Output is correct
2 Correct 258 ms 77872 KB Output is correct
3 Correct 234 ms 77136 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 20288 KB Output is correct
2 Correct 258 ms 77872 KB Output is correct
3 Correct 234 ms 77136 KB Output is correct
4 Incorrect 76 ms 20048 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 76 ms 20300 KB Output is correct
2 Correct 248 ms 84564 KB Output is correct
3 Correct 254 ms 84664 KB Output is correct
4 Execution timed out 3578 ms 84900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 76 ms 20300 KB Output is correct
2 Correct 248 ms 84564 KB Output is correct
3 Correct 254 ms 84664 KB Output is correct
4 Execution timed out 3578 ms 84900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 20332 KB Output is correct
2 Correct 114 ms 22132 KB Output is correct
3 Correct 61 ms 21960 KB Output is correct
4 Correct 538 ms 22256 KB Output is correct
5 Correct 819 ms 22548 KB Output is correct
6 Correct 67 ms 22220 KB Output is correct
7 Correct 61 ms 20300 KB Output is correct
8 Correct 256 ms 77764 KB Output is correct
9 Correct 237 ms 77760 KB Output is correct
10 Correct 76 ms 20232 KB Output is correct
11 Correct 219 ms 84528 KB Output is correct
12 Correct 229 ms 84744 KB Output is correct
13 Execution timed out 3576 ms 85100 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 20332 KB Output is correct
2 Correct 114 ms 22132 KB Output is correct
3 Correct 61 ms 21960 KB Output is correct
4 Correct 538 ms 22256 KB Output is correct
5 Correct 819 ms 22548 KB Output is correct
6 Correct 67 ms 22220 KB Output is correct
7 Correct 61 ms 20300 KB Output is correct
8 Correct 256 ms 77764 KB Output is correct
9 Correct 237 ms 77760 KB Output is correct
10 Correct 76 ms 20232 KB Output is correct
11 Correct 219 ms 84528 KB Output is correct
12 Correct 229 ms 84744 KB Output is correct
13 Execution timed out 3576 ms 85100 KB Time limit exceeded
14 Halted 0 ms 0 KB -