oj.uz

Submission #655312

# Submission time Handle Problem Language Result Execution time Memory
655312 2022-11-03T19:53:38 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 85144 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);
                              //  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 59 ms 20236 KB Output is correct
2 Correct 93 ms 22108 KB Output is correct
3 Correct 60 ms 21992 KB Output is correct
4 Correct 512 ms 22268 KB Output is correct
5 Correct 758 ms 22476 KB Output is correct
6 Correct 59 ms 22312 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 20236 KB Output is correct
2 Correct 93 ms 22108 KB Output is correct
3 Correct 60 ms 21992 KB Output is correct
4 Correct 512 ms 22268 KB Output is correct
5 Correct 758 ms 22476 KB Output is correct
6 Correct 59 ms 22312 KB Output is correct
7 Incorrect 61 ms 20060 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 20292 KB Output is correct
2 Correct 204 ms 77760 KB Output is correct
3 Correct 210 ms 77744 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 20292 KB Output is correct
2 Correct 204 ms 77760 KB Output is correct
3 Correct 210 ms 77744 KB Output is correct
4 Incorrect 45 ms 20008 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 69 ms 20252 KB Output is correct
2 Correct 210 ms 84536 KB Output is correct
3 Correct 226 ms 84744 KB Output is correct
4 Execution timed out 3581 ms 85080 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 20252 KB Output is correct
2 Correct 210 ms 84536 KB Output is correct
3 Correct 226 ms 84744 KB Output is correct
4 Execution timed out 3581 ms 85080 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 247 ms 77884 KB Output is correct
3 Correct 201 ms 77148 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 247 ms 77884 KB Output is correct
3 Correct 201 ms 77148 KB Output is correct
4 Incorrect 59 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 70 ms 20296 KB Output is correct
2 Correct 209 ms 84580 KB Output is correct
3 Correct 236 ms 84732 KB Output is correct
4 Execution timed out 3563 ms 85144 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 20296 KB Output is correct
2 Correct 209 ms 84580 KB Output is correct
3 Correct 236 ms 84732 KB Output is correct
4 Execution timed out 3563 ms 85144 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 20236 KB Output is correct
2 Correct 88 ms 22120 KB Output is correct
3 Correct 57 ms 21972 KB Output is correct
4 Correct 511 ms 22256 KB Output is correct
5 Correct 765 ms 22436 KB Output is correct
6 Correct 58 ms 22220 KB Output is correct
7 Correct 49 ms 20368 KB Output is correct
8 Correct 213 ms 77772 KB Output is correct
9 Correct 214 ms 77760 KB Output is correct
10 Correct 70 ms 20236 KB Output is correct
11 Correct 211 ms 84640 KB Output is correct
12 Correct 207 ms 84764 KB Output is correct
13 Execution timed out 3572 ms 85056 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 20236 KB Output is correct
2 Correct 88 ms 22120 KB Output is correct
3 Correct 57 ms 21972 KB Output is correct
4 Correct 511 ms 22256 KB Output is correct
5 Correct 765 ms 22436 KB Output is correct
6 Correct 58 ms 22220 KB Output is correct
7 Correct 49 ms 20368 KB Output is correct
8 Correct 213 ms 77772 KB Output is correct
9 Correct 214 ms 77760 KB Output is correct
10 Correct 70 ms 20236 KB Output is correct
11 Correct 211 ms 84640 KB Output is correct
12 Correct 207 ms 84764 KB Output is correct
13 Execution timed out 3572 ms 85056 KB Time limit exceeded
14 Halted 0 ms 0 KB -