oj.uz

Submission #578331

# Submission time Handle Problem Language Result Execution time Memory
578331 2022-06-16T11:35:34 Z mosiashvililuka Tropical Garden (IOI11_garden) C++14
100 / 100
 3389 ms 48088 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,L[300009],LL[300009],P,K,pas,bo[300009],msh[300009],MSH[300009],msh2[300009],MSH2[300009],cik[300009],zm[300009],N,p[300009],pi,la[300009],E,A,lf[300009],rg[300009],tim,cmp[300009],nmb[300009];
int up[300009],WI[300009];
vector <int> v[300009];
vector <pair <int, int> > VP[300009];
/*void dfs(int q, int rr){
    int qa=q/2;
    if(rr==K){
        if(bo[qa]!=t&&q%2==0){
            bo[qa]=t;pas++;
        }
        return;
    }
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        dfs((*it),rr+1);
    }
}*/
bool anc(int q, int w){
    if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
int dis(int q, int w, int rr){
    if(w>=q) return w-q;
    return rr+w-q;
}
void fun(int q){
    /*if(cik[q]==0){
        dfs(q,0);
        return;
    }
    int c=q,rr=0;
    while(1){
        if(rr>K) break;
        E=K-rr;
        A=c;
        DFS(c,0);
        if(WI[c]==q){
            break;
        }else{
            c=WI[c];rr++;
        }
    }*/
    if(cik[q]==0){
        for(i=2; i<=N; i+=2){
            if(bo[i]==t) continue;
            if(anc(q,i)==0) continue;
            if(up[i]==up[q]+K){
                bo[i]=t;pas++;
            }
        }
        return;
    }
    for(i=2; i<=N; i+=2){
        if(bo[i]==t) continue;
        if(cmp[q]!=cmp[i]) continue;
        zx=up[i]+dis(nmb[i],nmb[q],zm[q]);
        if(zx>K) continue;
        xc=K-zx;
        if(xc%zm[q]==0){
            bo[i]=t;pas++;
        }
    }
}
void dfs(int q, int w){
    if(w!=0){
        cmp[q]=cmp[w];nmb[q]=nmb[w];up[q]=up[w]+1;
    }
    tim++;lf[q]=rg[q]=tim;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if(cik[(*it)]==1) continue;
        dfs((*it),q);
        if(rg[q]<rg[(*it)]) rg[q]=rg[(*it)];
    }
}
void count_routes(int NN, int MM, int PP, int RR[][2], int QQ, int GG[])
{
    a=NN;b=MM;P=PP+1;tes=QQ;
    for(i=1; i<=a; i++){
        L[i]=b+5;
    }
    for(i=1; i<=b; i++){
        c=RR[i-1][0]+1;d=RR[i-1][1]+1;
        VP[c].push_back({i,d});
        VP[d].push_back({i,c});
        if(L[c]==b+5){
            L[c]=i;LL[c]=d;
        }
        if(L[d]==b+5){
            L[d]=i;LL[d]=c;
        }
    }
    for(i=1; i<=a; i++){
        sort(VP[i].begin(),VP[i].end());
        msh[i]=VP[i][0].second;MSH[i]=VP[i][0].first;
        if(VP[i].size()==1){
            msh2[i]=VP[i][0].second;MSH2[i]=VP[i][0].first;
        }else{
            msh2[i]=VP[i][1].second;MSH2[i]=VP[i][1].first;
        }
    }
    for(i=1; i<=a; i++){
        ii=0;
        if(L[msh[i]]!=MSH[i]){
            j=msh[i];jj=0;
        }else{
            j=msh[i];jj=1;
        }
        v[j*2+jj].push_back(i*2+ii);
        up[i*2+ii]=j*2+jj;
        ii=1;
        if(L[msh2[i]]!=MSH2[i]){
            j=msh2[i];jj=0;
        }else{
            j=msh2[i];jj=1;
        }
        v[j*2+jj].push_back(i*2+ii);
        up[i*2+ii]=j*2+jj;
    }
    /*for(t=1; t<=tes; t++){
        K=GG[t-1];pas=0;
        dfs(P*2,0);dfs(P*2+1,0);
        answer(pas);
    }*/
    N=a*2+1;
    for(i=0; i<=N+1; i++){
        bo[i]=0;msh[i]=up[i];
    }
    for(i=2; i<=N; i++){
        if(bo[i]!=0) continue;
        c=i;pi=0;
        while(1){
            pi++;p[pi]=c;bo[c]=1;la[c]=pi;
            if(bo[msh[c]]==0){
                c=msh[c];
                continue;
            }
            if(bo[msh[c]]==2){
                for(j=1; j<=pi; j++){
                    bo[p[j]]=2;
                }
                break;
            }
            if(bo[msh[c]]==1){
                for(j=la[msh[c]]; j<=pi; j++){
                    cik[p[j]]=1;zm[p[j]]=pi-la[msh[c]]+1;
                }
                for(j=1; j<=pi; j++){
                    bo[p[j]]=2;
                }
                /*for(j=2; j<=pi; j++){
                    WI[p[j]]=p[j-1];
                }
                WI[p[1]]=p[pi];*/
                for(j=la[msh[c]]+1; j<=pi; j++){
                    WI[p[j]]=p[j-1];
                }
                WI[p[la[msh[c]]]]=p[pi];
                break;
            }
        }
    }
    //
    for(i=0; i<=N+1; i++) bo[i]=0;
    zx=0;
    for(i=2; i<=N; i++){
        if(bo[i]!=0) continue;
        if(cik[i]==0) continue;
        c=i;zx++;xc=zm[i]+1;
        while(1){
            xc--;
            bo[c]=1;cmp[c]=zx;nmb[c]=xc;up[c]=0;
            if(WI[c]==i) break;
            c=WI[c];
        }
    }
    for(i=2; i<=N; i++){
        if(cik[i]==0) continue;
        dfs(i,0);
    }



    //
    for(i=0; i<=N+1; i++){
        bo[i]=0;
    }
    for(t=1; t<=tes; t++){
        K=GG[t-1];pas=0;
        fun(P*2);fun(P*2+1);
        /*for(i=2; i<=N; i++){
            if(i%2==0&&bo[i]==t) pas++;
        }*/
        answer(pas);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14716 KB Output is correct
2 Correct 8 ms 14676 KB Output is correct
3 Correct 8 ms 14656 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 10 ms 14804 KB Output is correct
7 Correct 10 ms 14532 KB Output is correct
8 Correct 9 ms 14572 KB Output is correct
9 Correct 10 ms 14932 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14716 KB Output is correct
2 Correct 8 ms 14676 KB Output is correct
3 Correct 8 ms 14656 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 10 ms 14804 KB Output is correct
7 Correct 10 ms 14532 KB Output is correct
8 Correct 9 ms 14572 KB Output is correct
9 Correct 10 ms 14932 KB Output is correct
10 Correct 8 ms 14536 KB Output is correct
11 Correct 21 ms 18768 KB Output is correct
12 Correct 42 ms 21764 KB Output is correct
13 Correct 51 ms 33800 KB Output is correct
14 Correct 141 ms 37948 KB Output is correct
15 Correct 142 ms 38472 KB Output is correct
16 Correct 122 ms 32316 KB Output is correct
17 Correct 108 ms 30360 KB Output is correct
18 Correct 36 ms 22096 KB Output is correct
19 Correct 126 ms 37956 KB Output is correct
20 Correct 135 ms 38472 KB Output is correct
21 Correct 129 ms 32588 KB Output is correct
22 Correct 105 ms 30480 KB Output is correct
23 Correct 134 ms 40524 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14716 KB Output is correct
2 Correct 8 ms 14676 KB Output is correct
3 Correct 8 ms 14656 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 10 ms 14804 KB Output is correct
7 Correct 10 ms 14532 KB Output is correct
8 Correct 9 ms 14572 KB Output is correct
9 Correct 10 ms 14932 KB Output is correct
10 Correct 8 ms 14536 KB Output is correct
11 Correct 21 ms 18768 KB Output is correct
12 Correct 42 ms 21764 KB Output is correct
13 Correct 51 ms 33800 KB Output is correct
14 Correct 141 ms 37948 KB Output is correct
15 Correct 142 ms 38472 KB Output is correct
16 Correct 122 ms 32316 KB Output is correct
17 Correct 108 ms 30360 KB Output is correct
18 Correct 36 ms 22096 KB Output is correct
19 Correct 126 ms 37956 KB Output is correct
20 Correct 135 ms 38472 KB Output is correct
21 Correct 129 ms 32588 KB Output is correct
22 Correct 105 ms 30480 KB Output is correct
23 Correct 134 ms 40524 KB Output is correct
24 Correct 9 ms 14548 KB Output is correct
25 Correct 120 ms 18892 KB Output is correct
26 Correct 203 ms 21784 KB Output is correct
27 Correct 2361 ms 33940 KB Output is correct
28 Correct 1198 ms 38220 KB Output is correct
29 Correct 3124 ms 38580 KB Output is correct
30 Correct 1654 ms 32360 KB Output is correct
31 Correct 2154 ms 30484 KB Output is correct
32 Correct 467 ms 21836 KB Output is correct
33 Correct 1188 ms 38092 KB Output is correct
34 Correct 3139 ms 38568 KB Output is correct
35 Correct 2459 ms 32544 KB Output is correct
36 Correct 2352 ms 30436 KB Output is correct
37 Correct 930 ms 40700 KB Output is correct
38 Correct 3389 ms 48088 KB Output is correct