oj.uz

Submission #655313

# Submission time Handle Problem Language Result Execution time Memory
655313 2022-11-03T19:54:30 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 85360 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{
                                assert(x!=z);
                                assert(dep[x]-dep[z]-1>=0);
                              //  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 63 ms 20232 KB Output is correct
2 Correct 100 ms 22176 KB Output is correct
3 Correct 60 ms 21984 KB Output is correct
4 Correct 500 ms 22256 KB Output is correct
5 Correct 752 ms 22444 KB Output is correct
6 Correct 58 ms 22224 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 20232 KB Output is correct
2 Correct 100 ms 22176 KB Output is correct
3 Correct 60 ms 21984 KB Output is correct
4 Correct 500 ms 22256 KB Output is correct
5 Correct 752 ms 22444 KB Output is correct
6 Correct 58 ms 22224 KB Output is correct
7 Incorrect 58 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 47 ms 20332 KB Output is correct
2 Correct 216 ms 77764 KB Output is correct
3 Correct 223 ms 77756 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 20332 KB Output is correct
2 Correct 216 ms 77764 KB Output is correct
3 Correct 223 ms 77756 KB Output is correct
4 Incorrect 45 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 70 ms 20288 KB Output is correct
2 Correct 220 ms 84612 KB Output is correct
3 Correct 229 ms 84760 KB Output is correct
4 Execution timed out 3593 ms 85028 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 20288 KB Output is correct
2 Correct 220 ms 84612 KB Output is correct
3 Correct 229 ms 84760 KB Output is correct
4 Execution timed out 3593 ms 85028 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 20300 KB Output is correct
2 Correct 224 ms 77880 KB Output is correct
3 Correct 210 ms 77136 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 20300 KB Output is correct
2 Correct 224 ms 77880 KB Output is correct
3 Correct 210 ms 77136 KB Output is correct
4 Incorrect 61 ms 20124 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 20232 KB Output is correct
2 Correct 213 ms 84556 KB Output is correct
3 Correct 213 ms 84708 KB Output is correct
4 Execution timed out 3593 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 20232 KB Output is correct
2 Correct 213 ms 84556 KB Output is correct
3 Correct 213 ms 84708 KB Output is correct
4 Execution timed out 3593 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 20300 KB Output is correct
2 Correct 89 ms 22184 KB Output is correct
3 Correct 62 ms 22004 KB Output is correct
4 Correct 516 ms 22344 KB Output is correct
5 Correct 768 ms 22440 KB Output is correct
6 Correct 63 ms 22136 KB Output is correct
7 Correct 48 ms 20244 KB Output is correct
8 Correct 211 ms 77768 KB Output is correct
9 Correct 231 ms 77820 KB Output is correct
10 Correct 72 ms 20300 KB Output is correct
11 Correct 211 ms 84596 KB Output is correct
12 Correct 210 ms 84848 KB Output is correct
13 Execution timed out 3568 ms 85360 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 22184 KB Output is correct
3 Correct 62 ms 22004 KB Output is correct
4 Correct 516 ms 22344 KB Output is correct
5 Correct 768 ms 22440 KB Output is correct
6 Correct 63 ms 22136 KB Output is correct
7 Correct 48 ms 20244 KB Output is correct
8 Correct 211 ms 77768 KB Output is correct
9 Correct 231 ms 77820 KB Output is correct
10 Correct 72 ms 20300 KB Output is correct
11 Correct 211 ms 84596 KB Output is correct
12 Correct 210 ms 84848 KB Output is correct
13 Execution timed out 3568 ms 85360 KB Time limit exceeded
14 Halted 0 ms 0 KB -