oj.uz

Submission #577982

# Submission time Handle Problem Language Result Execution time Memory
577982 2022-06-15T17:37:21 Z mosiashvililuka Tropical Garden (IOI11_garden) C++14
49 / 100
 303 ms 262144 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],LL[150009],P,K,pas,bo[300009],msh[150009],MSH[150009],msh2[150009],MSH2[150009];
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);
    }
}
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);
        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);
    }
    for(t=1; t<=tes; t++){
        K=GG[t-1];pas=0;
        dfs(P*2,0);dfs(P*2+1,0);
        answer(pas);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14408 KB Output is correct
6 Correct 8 ms 14540 KB Output is correct
7 Correct 8 ms 14428 KB Output is correct
8 Correct 9 ms 14456 KB Output is correct
9 Correct 11 ms 14820 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14408 KB Output is correct
6 Correct 8 ms 14540 KB Output is correct
7 Correct 8 ms 14428 KB Output is correct
8 Correct 9 ms 14456 KB Output is correct
9 Correct 11 ms 14820 KB Output is correct
10 Correct 9 ms 14656 KB Output is correct
11 Correct 67 ms 48324 KB Output is correct
12 Correct 303 ms 81944 KB Output is correct
13 Runtime error 204 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14408 KB Output is correct
6 Correct 8 ms 14540 KB Output is correct
7 Correct 8 ms 14428 KB Output is correct
8 Correct 9 ms 14456 KB Output is correct
9 Correct 11 ms 14820 KB Output is correct
10 Correct 9 ms 14656 KB Output is correct
11 Correct 67 ms 48324 KB Output is correct
12 Correct 303 ms 81944 KB Output is correct
13 Runtime error 204 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -