oj.uz

Submission #577480

# Submission time Handle Problem Language Result Execution time Memory
577480 2022-06-14T20:14:10 Z mosiashvililuka Tropical Garden (IOI11_garden) C++14
69 / 100
 293 ms 88124 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[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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct
4 Correct 3 ms 3836 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 4 ms 4436 KB Output is correct
7 Correct 3 ms 3836 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 7 ms 4676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct
4 Correct 3 ms 3836 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 4 ms 4436 KB Output is correct
7 Correct 3 ms 3836 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 7 ms 4676 KB Output is correct
10 Correct 2 ms 3832 KB Output is correct
11 Correct 40 ms 16368 KB Output is correct
12 Correct 63 ms 25632 KB Output is correct
13 Correct 173 ms 51124 KB Output is correct
14 Correct 264 ms 80040 KB Output is correct
15 Correct 265 ms 81140 KB Output is correct
16 Correct 174 ms 57292 KB Output is correct
17 Correct 161 ms 49640 KB Output is correct
18 Correct 71 ms 25548 KB Output is correct
19 Correct 266 ms 79948 KB Output is correct
20 Correct 237 ms 81120 KB Output is correct
21 Correct 188 ms 57144 KB Output is correct
22 Correct 174 ms 49456 KB Output is correct
23 Correct 293 ms 88124 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct
4 Correct 3 ms 3836 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 4 ms 4436 KB Output is correct
7 Correct 3 ms 3836 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 7 ms 4676 KB Output is correct
10 Correct 2 ms 3832 KB Output is correct
11 Correct 40 ms 16368 KB Output is correct
12 Correct 63 ms 25632 KB Output is correct
13 Correct 173 ms 51124 KB Output is correct
14 Correct 264 ms 80040 KB Output is correct
15 Correct 265 ms 81140 KB Output is correct
16 Correct 174 ms 57292 KB Output is correct
17 Correct 161 ms 49640 KB Output is correct
18 Correct 71 ms 25548 KB Output is correct
19 Correct 266 ms 79948 KB Output is correct
20 Correct 237 ms 81120 KB Output is correct
21 Correct 188 ms 57144 KB Output is correct
22 Correct 174 ms 49456 KB Output is correct
23 Correct 293 ms 88124 KB Output is correct
24 Incorrect 3 ms 3924 KB Output isn't correct
25 Halted 0 ms 0 KB -