oj.uz

Submission #655558

# Submission time Handle Problem Language Result Execution time Memory
655558 2022-11-04T17:47:31 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 86364 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=240000+7;
const int K = 20;
int n;
int k;
vector<pair<int, int>> gg[N];
vector<pair<int,int>> q2[N];
int q1[N];
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];
vector<int> who_have_id[N];
int who_has_id[N];

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;
        }
        who_has_id[i]=b;
        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];
int cnt[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() {
if(1) ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
else 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"){
                        tp[i]=2;
                        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[i]=a;
                        sol[i]=-3;
                        tp[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;
                }
        }

        const int INF=(int)1e9+7;

        int cnt_2=0;

        for (int i=1;i<=n+k-1;i++){
                if(tp[i]==2){
                        cnt_2++;
                        /// add edge
                        int vertex=who_has_id[i];
                        assert(2<=vertex&&vertex<=n);
                        while (1) {
                                cnt[vertex]++;
                                if(p[vertex]&&idup[p[vertex]]<idup[vertex]){
                                        vertex=p[vertex];
                                }else{
                                        break;
                                }
                        }

                }
                if (q1[i]){
                        int vertex=q1[i];
                        int ret=cnt[vertex]+1,last=-INF;
                        while (p[vertex]){
                                if ((idup[vertex]<last)){
                                        break;
                                }
                                last=idup[vertex];
                                for (auto &it:gg[p[vertex]]){
                                        int vecin=it.first;
                                        if(vecin!=vertex && idup[vertex]<idup[vecin]){
                                                ret+=cnt[vecin];
                                        }
                                }
                                vertex=p[vertex];
                        }
                        sol[i]=ret;
                }
        }
        assert(cnt_2==n-1);


        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";
                        }
                }
                if (tp[i]==3){
                        cout<<0<<"\n";
                }
        }

        return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:117:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 | else freopen("___input___.txt","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 20588 KB Output is correct
2 Correct 66 ms 22712 KB Output is correct
3 Correct 59 ms 22500 KB Output is correct
4 Correct 60 ms 22820 KB Output is correct
5 Correct 50 ms 22500 KB Output is correct
6 Correct 56 ms 22448 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 20588 KB Output is correct
2 Correct 66 ms 22712 KB Output is correct
3 Correct 59 ms 22500 KB Output is correct
4 Correct 60 ms 22820 KB Output is correct
5 Correct 50 ms 22500 KB Output is correct
6 Correct 56 ms 22448 KB Output is correct
7 Incorrect 44 ms 20556 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 45 ms 20496 KB Output is correct
2 Correct 222 ms 80064 KB Output is correct
3 Correct 237 ms 80132 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 20496 KB Output is correct
2 Correct 222 ms 80064 KB Output is correct
3 Correct 237 ms 80132 KB Output is correct
4 Incorrect 46 ms 20608 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 40 ms 20496 KB Output is correct
2 Correct 219 ms 86320 KB Output is correct
3 Correct 236 ms 86308 KB Output is correct
4 Execution timed out 3582 ms 86188 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 20496 KB Output is correct
2 Correct 219 ms 86320 KB Output is correct
3 Correct 236 ms 86308 KB Output is correct
4 Execution timed out 3582 ms 86188 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20480 KB Output is correct
2 Correct 224 ms 80000 KB Output is correct
3 Correct 210 ms 79672 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20480 KB Output is correct
2 Correct 224 ms 80000 KB Output is correct
3 Correct 210 ms 79672 KB Output is correct
4 Incorrect 44 ms 20548 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 52 ms 20444 KB Output is correct
2 Correct 235 ms 86300 KB Output is correct
3 Correct 214 ms 86364 KB Output is correct
4 Execution timed out 3583 ms 86152 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 20444 KB Output is correct
2 Correct 235 ms 86300 KB Output is correct
3 Correct 214 ms 86364 KB Output is correct
4 Execution timed out 3583 ms 86152 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20448 KB Output is correct
2 Correct 65 ms 22720 KB Output is correct
3 Correct 63 ms 22520 KB Output is correct
4 Correct 61 ms 22824 KB Output is correct
5 Correct 57 ms 22568 KB Output is correct
6 Correct 57 ms 22444 KB Output is correct
7 Correct 50 ms 20556 KB Output is correct
8 Correct 253 ms 80120 KB Output is correct
9 Correct 273 ms 80096 KB Output is correct
10 Correct 42 ms 20460 KB Output is correct
11 Correct 223 ms 86344 KB Output is correct
12 Correct 209 ms 86260 KB Output is correct
13 Execution timed out 3595 ms 86180 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20448 KB Output is correct
2 Correct 65 ms 22720 KB Output is correct
3 Correct 63 ms 22520 KB Output is correct
4 Correct 61 ms 22824 KB Output is correct
5 Correct 57 ms 22568 KB Output is correct
6 Correct 57 ms 22444 KB Output is correct
7 Correct 50 ms 20556 KB Output is correct
8 Correct 253 ms 80120 KB Output is correct
9 Correct 273 ms 80096 KB Output is correct
10 Correct 42 ms 20460 KB Output is correct
11 Correct 223 ms 86344 KB Output is correct
12 Correct 209 ms 86260 KB Output is correct
13 Execution timed out 3595 ms 86180 KB Time limit exceeded
14 Halted 0 ms 0 KB -