oj.uz

Submission #655326

# Submission time Handle Problem Language Result Execution time Memory
655326 2022-11-03T20:19:50 Z 600Mihnea Inside information (BOI21_servers) C++17
50 / 100
 274 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;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{
                                last=idup[goup(x,dep[x]-dep[z]-1)];
                        }
                        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)]);
                        }
                        ok&=(last<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 44 ms 20308 KB Output is correct
2 Correct 58 ms 22196 KB Output is correct
3 Correct 58 ms 22004 KB Output is correct
4 Correct 58 ms 22344 KB Output is correct
5 Correct 51 ms 22460 KB Output is correct
6 Correct 61 ms 22212 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20308 KB Output is correct
2 Correct 58 ms 22196 KB Output is correct
3 Correct 58 ms 22004 KB Output is correct
4 Correct 58 ms 22344 KB Output is correct
5 Correct 51 ms 22460 KB Output is correct
6 Correct 61 ms 22212 KB Output is correct
7 Incorrect 44 ms 20044 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 43 ms 20344 KB Output is correct
2 Correct 228 ms 78652 KB Output is correct
3 Correct 214 ms 78712 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20344 KB Output is correct
2 Correct 228 ms 78652 KB Output is correct
3 Correct 214 ms 78712 KB Output is correct
4 Incorrect 43 ms 20044 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 20364 KB Output is correct
2 Correct 223 ms 84872 KB Output is correct
3 Correct 219 ms 84912 KB Output is correct
4 Correct 193 ms 85360 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 20364 KB Output is correct
2 Correct 223 ms 84872 KB Output is correct
3 Correct 219 ms 84912 KB Output is correct
4 Correct 193 ms 85360 KB Output is correct
5 Incorrect 42 ms 20992 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20332 KB Output is correct
2 Correct 199 ms 78840 KB Output is correct
3 Correct 211 ms 78260 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20332 KB Output is correct
2 Correct 199 ms 78840 KB Output is correct
3 Correct 211 ms 78260 KB Output is correct
4 Incorrect 43 ms 20040 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 20264 KB Output is correct
2 Correct 220 ms 84872 KB Output is correct
3 Correct 219 ms 84956 KB Output is correct
4 Correct 183 ms 85276 KB Output is correct
5 Correct 44 ms 21196 KB Output is correct
6 Correct 208 ms 82064 KB Output is correct
7 Correct 216 ms 81360 KB Output is correct
8 Correct 270 ms 82980 KB Output is correct
9 Correct 245 ms 82420 KB Output is correct
10 Correct 236 ms 85232 KB Output is correct
11 Correct 274 ms 84488 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 20264 KB Output is correct
2 Correct 220 ms 84872 KB Output is correct
3 Correct 219 ms 84956 KB Output is correct
4 Correct 183 ms 85276 KB Output is correct
5 Correct 44 ms 21196 KB Output is correct
6 Correct 208 ms 82064 KB Output is correct
7 Correct 216 ms 81360 KB Output is correct
8 Correct 270 ms 82980 KB Output is correct
9 Correct 245 ms 82420 KB Output is correct
10 Correct 236 ms 85232 KB Output is correct
11 Correct 274 ms 84488 KB Output is correct
12 Incorrect 43 ms 20912 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 20300 KB Output is correct
2 Correct 68 ms 22168 KB Output is correct
3 Correct 55 ms 22016 KB Output is correct
4 Correct 60 ms 22220 KB Output is correct
5 Correct 52 ms 22432 KB Output is correct
6 Correct 55 ms 22264 KB Output is correct
7 Correct 46 ms 20300 KB Output is correct
8 Correct 218 ms 78680 KB Output is correct
9 Correct 232 ms 78756 KB Output is correct
10 Correct 42 ms 20360 KB Output is correct
11 Correct 213 ms 84940 KB Output is correct
12 Correct 219 ms 84980 KB Output is correct
13 Correct 196 ms 85304 KB Output is correct
14 Correct 48 ms 21196 KB Output is correct
15 Correct 211 ms 82096 KB Output is correct
16 Correct 214 ms 81420 KB Output is correct
17 Correct 251 ms 83020 KB Output is correct
18 Correct 247 ms 82496 KB Output is correct
19 Correct 214 ms 85272 KB Output is correct
20 Correct 246 ms 84624 KB Output is correct
21 Correct 261 ms 82064 KB Output is correct
22 Correct 220 ms 82100 KB Output is correct
23 Correct 229 ms 82348 KB Output is correct
24 Correct 255 ms 82412 KB Output is correct
25 Correct 256 ms 83396 KB Output is correct
26 Correct 206 ms 80484 KB Output is correct
27 Correct 226 ms 80180 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 20300 KB Output is correct
2 Correct 68 ms 22168 KB Output is correct
3 Correct 55 ms 22016 KB Output is correct
4 Correct 60 ms 22220 KB Output is correct
5 Correct 52 ms 22432 KB Output is correct
6 Correct 55 ms 22264 KB Output is correct
7 Correct 46 ms 20300 KB Output is correct
8 Correct 218 ms 78680 KB Output is correct
9 Correct 232 ms 78756 KB Output is correct
10 Correct 42 ms 20360 KB Output is correct
11 Correct 213 ms 84940 KB Output is correct
12 Correct 219 ms 84980 KB Output is correct
13 Correct 196 ms 85304 KB Output is correct
14 Correct 48 ms 21196 KB Output is correct
15 Correct 211 ms 82096 KB Output is correct
16 Correct 214 ms 81420 KB Output is correct
17 Correct 251 ms 83020 KB Output is correct
18 Correct 247 ms 82496 KB Output is correct
19 Correct 214 ms 85272 KB Output is correct
20 Correct 246 ms 84624 KB Output is correct
21 Correct 261 ms 82064 KB Output is correct
22 Correct 220 ms 82100 KB Output is correct
23 Correct 229 ms 82348 KB Output is correct
24 Correct 255 ms 82412 KB Output is correct
25 Correct 256 ms 83396 KB Output is correct
26 Correct 206 ms 80484 KB Output is correct
27 Correct 226 ms 80180 KB Output is correct
28 Incorrect 45 ms 20940 KB Extra information in the output file
29 Halted 0 ms 0 KB -