Submission #577480

#	Time	Username	Problem	Language	Result	Execution time	Memory
577480		mosiashvililuka	Tropical Garden (IOI11_garden)	C++14	69 / 100	293 ms	88124 KiB

garden

#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[150009],P,msh[150009][32],msh2[150009][32],MSH[150009][32],MSH2[150009][32],K,pas;
vector <pair <int, int> > VP[150009];
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;
        L[c]=min(L[c],i);L[d]=min(L[d],i);
        VP[c].push_back({i,d});VP[d].push_back({i,c});
    }
    for(i=1; i<=a; i++){
        sort(VP[i].begin(),VP[i].end());
        msh[i][0]=VP[i][0].second;MSH[i][0]=VP[i][0].first;
        if(VP[i].size()==1){
            msh2[i][0]=msh[i][0];MSH2[i][0]=MSH[i][0];
        }else{
            msh2[i][0]=VP[i][1].second;MSH2[i][0]=VP[i][1].first;
        }
    }
    for(j=1; j<=30; j++){
        for(i=1; i<=a; i++){
            c=msh[i][j-1];d=MSH[i][j-1];
            if(L[c]!=d){
                msh[i][j]=msh[c][j-1];
                MSH[i][j]=MSH[c][j-1];
            }else{
                msh[i][j]=msh2[c][j-1];
                MSH[i][j]=MSH2[c][j-1];
            }
            c=msh2[i][j-1];d=MSH2[i][j-1];
            if(L[c]!=d){
                msh2[i][j]=msh[c][j-1];
                MSH2[i][j]=MSH[c][j-1];
            }else{
                msh2[i][j]=msh2[c][j-1];
                MSH2[i][j]=MSH2[c][j-1];
            }
        }
    }
    K=GG[0];
    pas=0;
    for(i=1; i<=a; i++){
        c=i;d=-2;
        for(j=0; j<=30; j++){
            if((K&(1<<j))==0) continue;
            if(L[c]!=d){
                zx=msh[c][j];xc=MSH[c][j];
            }else{
                zx=msh2[c][j];xc=MSH2[c][j];
            }
            c=zx;d=xc;
        }
        //cout<<i<<" I "<<c<<"\n";
        if(c==P){
            pas++;
        }
    }
    //cout<<"pasuxi: "<<pas<<"\n";
    answer(pas);
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31