oj.uz

Submission #578299

# Submission time Handle Problem Language Result Execution time Memory
578299 2022-06-16T10:33:34 Z mosiashvililuka Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 35912 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;
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);
    }
}*/
void dfs(int q, int rr){
    if(rr==K){
        bo[q]=t;
        return;
    }
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        dfs((*it),rr+1);
    }
}
void DFS(int q, int rr){
    if(rr>E) return;
    if(rr%zm[A]==E%zm[A]){
        bo[q]=t;
    }
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if(cik[(*it)]!=0) continue;
        DFS((*it),rr+1);
    }
}
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++;
        }
    }
}
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;
    }
    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 14548 KB Output is correct
2 Correct 8 ms 14560 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14516 KB Output is correct
5 Correct 8 ms 14392 KB Output is correct
6 Correct 9 ms 14664 KB Output is correct
7 Correct 8 ms 14488 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 10 ms 14804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14560 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14516 KB Output is correct
5 Correct 8 ms 14392 KB Output is correct
6 Correct 9 ms 14664 KB Output is correct
7 Correct 8 ms 14488 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 10 ms 14804 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 18 ms 18124 KB Output is correct
12 Correct 31 ms 20564 KB Output is correct
13 Correct 48 ms 31064 KB Output is correct
14 Correct 96 ms 33804 KB Output is correct
15 Correct 116 ms 34232 KB Output is correct
16 Correct 91 ms 29400 KB Output is correct
17 Correct 90 ms 27960 KB Output is correct
18 Correct 46 ms 20908 KB Output is correct
19 Correct 107 ms 33900 KB Output is correct
20 Correct 134 ms 34184 KB Output is correct
21 Correct 104 ms 29704 KB Output is correct
22 Correct 106 ms 27912 KB Output is correct
23 Correct 102 ms 35912 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14560 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14516 KB Output is correct
5 Correct 8 ms 14392 KB Output is correct
6 Correct 9 ms 14664 KB Output is correct
7 Correct 8 ms 14488 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 10 ms 14804 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 18 ms 18124 KB Output is correct
12 Correct 31 ms 20564 KB Output is correct
13 Correct 48 ms 31064 KB Output is correct
14 Correct 96 ms 33804 KB Output is correct
15 Correct 116 ms 34232 KB Output is correct
16 Correct 91 ms 29400 KB Output is correct
17 Correct 90 ms 27960 KB Output is correct
18 Correct 46 ms 20908 KB Output is correct
19 Correct 107 ms 33900 KB Output is correct
20 Correct 134 ms 34184 KB Output is correct
21 Correct 104 ms 29704 KB Output is correct
22 Correct 106 ms 27912 KB Output is correct
23 Correct 102 ms 35912 KB Output is correct
24 Correct 13 ms 14548 KB Output is correct
25 Correct 230 ms 18128 KB Output is correct
26 Correct 229 ms 20588 KB Output is correct
27 Execution timed out 5048 ms 31196 KB Time limit exceeded
28 Halted 0 ms 0 KB -