oj.uz

Submission #655304

# Submission time Handle Problem Language Result Execution time Memory
655304 2022-11-03T19:46:39 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 79808 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 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 = -1)
{
    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 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;
                        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;
                }
        }
        /// 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];
                        }
                        vector<int> guys=guys_x;
                        reverse(guys_y.begin(),guys_y.end());
                        for (auto &V:guys_y){
                                guys.push_back(V);
                        }
                        bool ok=1;
                        guys.push_back(i);
                       /* cout<< " ---> ";
                        for (auto &it : guys){
                                cout<<it<<" ";
                        }
                        cout<<"\n";*/
                        for (int it=1;it<(int)guys.size();it++){
                                ok&=(guys[it-1]<guys[it]);
                        }
                        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 74 ms 20144 KB Output is correct
2 Correct 98 ms 23100 KB Output is correct
3 Correct 67 ms 22976 KB Output is correct
4 Correct 578 ms 23264 KB Output is correct
5 Correct 841 ms 23456 KB Output is correct
6 Correct 61 ms 23116 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 20144 KB Output is correct
2 Correct 98 ms 23100 KB Output is correct
3 Correct 67 ms 22976 KB Output is correct
4 Correct 578 ms 23264 KB Output is correct
5 Correct 841 ms 23456 KB Output is correct
6 Correct 61 ms 23116 KB Output is correct
7 Incorrect 64 ms 20760 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 55 ms 20236 KB Output is correct
2 Correct 219 ms 71156 KB Output is correct
3 Correct 253 ms 71104 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 20236 KB Output is correct
2 Correct 219 ms 71156 KB Output is correct
3 Correct 253 ms 71104 KB Output is correct
4 Incorrect 52 ms 20760 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 20120 KB Output is correct
2 Correct 259 ms 79000 KB Output is correct
3 Correct 244 ms 79112 KB Output is correct
4 Execution timed out 3554 ms 79468 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 20120 KB Output is correct
2 Correct 259 ms 79000 KB Output is correct
3 Correct 244 ms 79112 KB Output is correct
4 Execution timed out 3554 ms 79468 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 20176 KB Output is correct
2 Correct 281 ms 71764 KB Output is correct
3 Correct 228 ms 71516 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 20176 KB Output is correct
2 Correct 281 ms 71764 KB Output is correct
3 Correct 228 ms 71516 KB Output is correct
4 Incorrect 74 ms 20768 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 77 ms 20196 KB Output is correct
2 Correct 258 ms 79016 KB Output is correct
3 Correct 233 ms 79124 KB Output is correct
4 Execution timed out 3571 ms 79712 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 77 ms 20196 KB Output is correct
2 Correct 258 ms 79016 KB Output is correct
3 Correct 233 ms 79124 KB Output is correct
4 Execution timed out 3571 ms 79712 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20212 KB Output is correct
2 Correct 108 ms 23084 KB Output is correct
3 Correct 68 ms 22904 KB Output is correct
4 Correct 533 ms 23216 KB Output is correct
5 Correct 791 ms 23500 KB Output is correct
6 Correct 67 ms 23212 KB Output is correct
7 Correct 57 ms 21112 KB Output is correct
8 Correct 218 ms 71156 KB Output is correct
9 Correct 230 ms 71108 KB Output is correct
10 Correct 81 ms 21008 KB Output is correct
11 Correct 233 ms 79048 KB Output is correct
12 Correct 251 ms 79100 KB Output is correct
13 Execution timed out 3554 ms 79808 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20212 KB Output is correct
2 Correct 108 ms 23084 KB Output is correct
3 Correct 68 ms 22904 KB Output is correct
4 Correct 533 ms 23216 KB Output is correct
5 Correct 791 ms 23500 KB Output is correct
6 Correct 67 ms 23212 KB Output is correct
7 Correct 57 ms 21112 KB Output is correct
8 Correct 218 ms 71156 KB Output is correct
9 Correct 230 ms 71108 KB Output is correct
10 Correct 81 ms 21008 KB Output is correct
11 Correct 233 ms 79048 KB Output is correct
12 Correct 251 ms 79100 KB Output is correct
13 Execution timed out 3554 ms 79808 KB Time limit exceeded
14 Halted 0 ms 0 KB -