oj.uz

Submission #655307

# Submission time Handle Problem Language Result Execution time Memory
655307 2022-11-03T19:51:14 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 85164 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);
                        while (x!=z){
                                guys_x.push_back(idup[x]);
                                x=p[x];
                        }
                        while(y!=z){
                                guys_y.push_back(idup[y]);
                                y=p[y];
                        }
                        int last=-1;

                        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 62 ms 20348 KB Output is correct
2 Correct 93 ms 22216 KB Output is correct
3 Correct 60 ms 21964 KB Output is correct
4 Correct 582 ms 22252 KB Output is correct
5 Correct 877 ms 22444 KB Output is correct
6 Correct 67 ms 22192 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20348 KB Output is correct
2 Correct 93 ms 22216 KB Output is correct
3 Correct 60 ms 21964 KB Output is correct
4 Correct 582 ms 22252 KB Output is correct
5 Correct 877 ms 22444 KB Output is correct
6 Correct 67 ms 22192 KB Output is correct
7 Incorrect 61 ms 20040 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 58 ms 20364 KB Output is correct
2 Correct 251 ms 77760 KB Output is correct
3 Correct 219 ms 77764 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 20364 KB Output is correct
2 Correct 251 ms 77760 KB Output is correct
3 Correct 219 ms 77764 KB Output is correct
4 Incorrect 53 ms 19992 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 20236 KB Output is correct
2 Correct 214 ms 84584 KB Output is correct
3 Correct 218 ms 84680 KB Output is correct
4 Execution timed out 3577 ms 85104 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 20236 KB Output is correct
2 Correct 214 ms 84584 KB Output is correct
3 Correct 218 ms 84680 KB Output is correct
4 Execution timed out 3577 ms 85104 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 20300 KB Output is correct
2 Correct 254 ms 77852 KB Output is correct
3 Correct 204 ms 77136 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 20300 KB Output is correct
2 Correct 254 ms 77852 KB Output is correct
3 Correct 204 ms 77136 KB Output is correct
4 Incorrect 60 ms 20012 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 20300 KB Output is correct
2 Correct 277 ms 84608 KB Output is correct
3 Correct 217 ms 84768 KB Output is correct
4 Execution timed out 3584 ms 85112 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 20300 KB Output is correct
2 Correct 277 ms 84608 KB Output is correct
3 Correct 217 ms 84768 KB Output is correct
4 Execution timed out 3584 ms 85112 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 20300 KB Output is correct
2 Correct 102 ms 22176 KB Output is correct
3 Correct 79 ms 21968 KB Output is correct
4 Correct 583 ms 22312 KB Output is correct
5 Correct 877 ms 22444 KB Output is correct
6 Correct 65 ms 22220 KB Output is correct
7 Correct 61 ms 20320 KB Output is correct
8 Correct 258 ms 77716 KB Output is correct
9 Correct 222 ms 77672 KB Output is correct
10 Correct 76 ms 20232 KB Output is correct
11 Correct 273 ms 84604 KB Output is correct
12 Correct 242 ms 84764 KB Output is correct
13 Execution timed out 3556 ms 85164 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 20300 KB Output is correct
2 Correct 102 ms 22176 KB Output is correct
3 Correct 79 ms 21968 KB Output is correct
4 Correct 583 ms 22312 KB Output is correct
5 Correct 877 ms 22444 KB Output is correct
6 Correct 65 ms 22220 KB Output is correct
7 Correct 61 ms 20320 KB Output is correct
8 Correct 258 ms 77716 KB Output is correct
9 Correct 222 ms 77672 KB Output is correct
10 Correct 76 ms 20232 KB Output is correct
11 Correct 273 ms 84604 KB Output is correct
12 Correct 242 ms 84764 KB Output is correct
13 Execution timed out 3556 ms 85164 KB Time limit exceeded
14 Halted 0 ms 0 KB -