oj.uz

Submission #655316

# Submission time Handle Problem Language Result Execution time Memory
655316 2022-11-03T19:58:46 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 85328 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 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();
        /// 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];
                        }
                        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());
                        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 68 ms 20300 KB Output is correct
2 Correct 88 ms 22112 KB Output is correct
3 Correct 57 ms 21964 KB Output is correct
4 Correct 505 ms 22260 KB Output is correct
5 Correct 774 ms 22444 KB Output is correct
6 Correct 58 ms 22220 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 20300 KB Output is correct
2 Correct 88 ms 22112 KB Output is correct
3 Correct 57 ms 21964 KB Output is correct
4 Correct 505 ms 22260 KB Output is correct
5 Correct 774 ms 22444 KB Output is correct
6 Correct 58 ms 22220 KB Output is correct
7 Incorrect 59 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 50 ms 20300 KB Output is correct
2 Correct 212 ms 77696 KB Output is correct
3 Correct 222 ms 77852 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 20300 KB Output is correct
2 Correct 212 ms 77696 KB Output is correct
3 Correct 222 ms 77852 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 73 ms 20232 KB Output is correct
2 Correct 214 ms 84544 KB Output is correct
3 Correct 211 ms 84696 KB Output is correct
4 Execution timed out 3568 ms 85192 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 20232 KB Output is correct
2 Correct 214 ms 84544 KB Output is correct
3 Correct 211 ms 84696 KB Output is correct
4 Execution timed out 3568 ms 85192 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 20232 KB Output is correct
2 Correct 226 ms 77880 KB Output is correct
3 Correct 205 ms 77140 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 20232 KB Output is correct
2 Correct 226 ms 77880 KB Output is correct
3 Correct 205 ms 77140 KB Output is correct
4 Incorrect 59 ms 20100 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 70 ms 20300 KB Output is correct
2 Correct 234 ms 84556 KB Output is correct
3 Correct 214 ms 84640 KB Output is correct
4 Execution timed out 3554 ms 85152 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 20300 KB Output is correct
2 Correct 234 ms 84556 KB Output is correct
3 Correct 214 ms 84640 KB Output is correct
4 Execution timed out 3554 ms 85152 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 20236 KB Output is correct
2 Correct 90 ms 22132 KB Output is correct
3 Correct 58 ms 21984 KB Output is correct
4 Correct 507 ms 22348 KB Output is correct
5 Correct 781 ms 22444 KB Output is correct
6 Correct 58 ms 22220 KB Output is correct
7 Correct 48 ms 20244 KB Output is correct
8 Correct 219 ms 77732 KB Output is correct
9 Correct 206 ms 77760 KB Output is correct
10 Correct 72 ms 20236 KB Output is correct
11 Correct 208 ms 84556 KB Output is correct
12 Correct 207 ms 84744 KB Output is correct
13 Execution timed out 3566 ms 85328 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 20236 KB Output is correct
2 Correct 90 ms 22132 KB Output is correct
3 Correct 58 ms 21984 KB Output is correct
4 Correct 507 ms 22348 KB Output is correct
5 Correct 781 ms 22444 KB Output is correct
6 Correct 58 ms 22220 KB Output is correct
7 Correct 48 ms 20244 KB Output is correct
8 Correct 219 ms 77732 KB Output is correct
9 Correct 206 ms 77760 KB Output is correct
10 Correct 72 ms 20236 KB Output is correct
11 Correct 208 ms 84556 KB Output is correct
12 Correct 207 ms 84744 KB Output is correct
13 Execution timed out 3566 ms 85328 KB Time limit exceeded
14 Halted 0 ms 0 KB -