oj.uz

Submission #578304

# Submission time Handle Problem Language Result Execution time Memory
578304 2022-06-16T10:50:35 Z mosiashvililuka Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 34148 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){
        if(bo[q]!=t&&q%2==0){
            bo[q]=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>E) return;
    if(bo[q]!=t&&q%2==0&&rr%zm[A]==E%zm[A]){
        bo[q]=t;pas++;
    }
    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 9 ms 14548 KB Output is correct
2 Correct 8 ms 14640 KB Output is correct
3 Correct 8 ms 14576 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 11 ms 14548 KB Output is correct
9 Correct 10 ms 14916 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 8 ms 14640 KB Output is correct
3 Correct 8 ms 14576 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 11 ms 14548 KB Output is correct
9 Correct 10 ms 14916 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 17 ms 17868 KB Output is correct
12 Correct 32 ms 19916 KB Output is correct
13 Correct 47 ms 30040 KB Output is correct
14 Correct 104 ms 32076 KB Output is correct
15 Correct 141 ms 32392 KB Output is correct
16 Correct 101 ms 27788 KB Output is correct
17 Correct 92 ms 26364 KB Output is correct
18 Correct 35 ms 20264 KB Output is correct
19 Correct 110 ms 32256 KB Output is correct
20 Correct 137 ms 32532 KB Output is correct
21 Correct 121 ms 28048 KB Output is correct
22 Correct 104 ms 26380 KB Output is correct
23 Correct 119 ms 34148 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 8 ms 14640 KB Output is correct
3 Correct 8 ms 14576 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 11 ms 14548 KB Output is correct
9 Correct 10 ms 14916 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 17 ms 17868 KB Output is correct
12 Correct 32 ms 19916 KB Output is correct
13 Correct 47 ms 30040 KB Output is correct
14 Correct 104 ms 32076 KB Output is correct
15 Correct 141 ms 32392 KB Output is correct
16 Correct 101 ms 27788 KB Output is correct
17 Correct 92 ms 26364 KB Output is correct
18 Correct 35 ms 20264 KB Output is correct
19 Correct 110 ms 32256 KB Output is correct
20 Correct 137 ms 32532 KB Output is correct
21 Correct 121 ms 28048 KB Output is correct
22 Correct 104 ms 26380 KB Output is correct
23 Correct 119 ms 34148 KB Output is correct
24 Correct 10 ms 14420 KB Output is correct
25 Correct 104 ms 17888 KB Output is correct
26 Correct 83 ms 19996 KB Output is correct
27 Execution timed out 5055 ms 30148 KB Time limit exceeded
28 Halted 0 ms 0 KB -