oj.uz

Submission #655325

# Submission time Handle Problem Language Result Execution time Memory
655325 2022-11-03T20:19:09 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 86104 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 inc[N];
int dcr[N];

void dfs2(int a){
        inc[a]=max(inc[a],1);
        dcr[a]=max(dcr[a],1);
        for (auto &it:gg[a]){
                int b=it.first;
                if(b==p[a]){
                        continue;
                }
                if(idup[a]<idup[b]){
                        inc[b]=1+inc[a];
                }else{
                        dcr[b]=1+dcr[a];
                }
                dfs2(b);
        }
        ///cout<<"vis "<<a<<" : "<<inc[a]<<" vs "<<dcr[a]<<"\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();
        dfs2(1);
        /// 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];
                        }
                        bool ok=1;
                        ok&=(inc[y]>=dep[y]-dep[z]);
                        ok&=(dcr[x]>=dep[x]-dep[z]);
                        if(x!=z&&y!=z){
                                ok&=(idup[goup(x,dep[x]-dep[z]-1)]<=idup[goup(y,dep[y]-dep[z]-1)]);
                        }
                        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);
                        }
                        assert(!guys.empty());
                        assert(guys.back()==last);
                        if(!guys_x.empty()&&!guys_y.empty()){
                              //  ok&=(guys_x.back()<=guys_y[0]);
                        }
                        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 20256 KB Output is correct
2 Correct 103 ms 22168 KB Output is correct
3 Correct 65 ms 22012 KB Output is correct
4 Correct 523 ms 22304 KB Output is correct
5 Correct 708 ms 22492 KB Output is correct
6 Correct 69 ms 22216 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 20256 KB Output is correct
2 Correct 103 ms 22168 KB Output is correct
3 Correct 65 ms 22012 KB Output is correct
4 Correct 523 ms 22304 KB Output is correct
5 Correct 708 ms 22492 KB Output is correct
6 Correct 69 ms 22216 KB Output is correct
7 Incorrect 70 ms 20032 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 54 ms 20268 KB Output is correct
2 Correct 238 ms 78656 KB Output is correct
3 Correct 242 ms 78712 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 20268 KB Output is correct
2 Correct 238 ms 78656 KB Output is correct
3 Correct 242 ms 78712 KB Output is correct
4 Incorrect 55 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 76 ms 20304 KB Output is correct
2 Correct 232 ms 85536 KB Output is correct
3 Correct 246 ms 85628 KB Output is correct
4 Execution timed out 3575 ms 86104 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 20304 KB Output is correct
2 Correct 232 ms 85536 KB Output is correct
3 Correct 246 ms 85628 KB Output is correct
4 Execution timed out 3575 ms 86104 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 20256 KB Output is correct
2 Correct 270 ms 78792 KB Output is correct
3 Correct 216 ms 78148 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 20256 KB Output is correct
2 Correct 270 ms 78792 KB Output is correct
3 Correct 216 ms 78148 KB Output is correct
4 Incorrect 72 ms 20028 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 74 ms 20344 KB Output is correct
2 Correct 261 ms 85580 KB Output is correct
3 Correct 250 ms 85660 KB Output is correct
4 Execution timed out 3585 ms 86064 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 20344 KB Output is correct
2 Correct 261 ms 85580 KB Output is correct
3 Correct 250 ms 85660 KB Output is correct
4 Execution timed out 3585 ms 86064 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 100 ms 22260 KB Output is correct
3 Correct 65 ms 21972 KB Output is correct
4 Correct 494 ms 22296 KB Output is correct
5 Correct 692 ms 22572 KB Output is correct
6 Correct 68 ms 22208 KB Output is correct
7 Correct 52 ms 20368 KB Output is correct
8 Correct 235 ms 78688 KB Output is correct
9 Correct 236 ms 78712 KB Output is correct
10 Correct 71 ms 20292 KB Output is correct
11 Correct 250 ms 85548 KB Output is correct
12 Correct 217 ms 85600 KB Output is correct
13 Execution timed out 3562 ms 86076 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 100 ms 22260 KB Output is correct
3 Correct 65 ms 21972 KB Output is correct
4 Correct 494 ms 22296 KB Output is correct
5 Correct 692 ms 22572 KB Output is correct
6 Correct 68 ms 22208 KB Output is correct
7 Correct 52 ms 20368 KB Output is correct
8 Correct 235 ms 78688 KB Output is correct
9 Correct 236 ms 78712 KB Output is correct
10 Correct 71 ms 20292 KB Output is correct
11 Correct 250 ms 85548 KB Output is correct
12 Correct 217 ms 85600 KB Output is correct
13 Execution timed out 3562 ms 86076 KB Time limit exceeded
14 Halted 0 ms 0 KB -