Submission #790439

#	Time	Username	Problem	Language	Result	Execution time	Memory
790439		kilikuma	Tropical Garden (IOI11_garden)	C++14	100 / 100	2421 ms	25684 KiB

garden

#include<bits/stdc++.h>
using namespace std;
const int N=400100;
typedef long long ll;

vector<int> listeCourante[N];
int pass[N],areteCourante[N],d0[N],d1[N];
void answer(int X);

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{

    for(int i=0;i<M;i++)
        areteCourante[R[i][0]]++,areteCourante[R[i][1]]++;
    for(int i=0;i<M;i++)
    {
        int u0=2*R[i][0],v0=2*R[i][1];
        if(pass[R[i][0]]<=1)
        {
            if(!pass[R[i][1]]){
                if(areteCourante[R[i][0]]==1){
                    listeCourante[v0+1].push_back(u0);
                    listeCourante[v0+1].push_back(u0+1);
                }else
                    listeCourante[v0+1].push_back(u0+pass[R[i][0]]);
            }else
            {

                if(areteCourante[R[i][0]]==1){
                    listeCourante[v0].push_back(u0);
                    listeCourante[v0].push_back(u0+1);
                }else
                    listeCourante[v0].push_back(u0+pass[R[i][0]]);
            }

        }
        if(pass[R[i][1]]<=1)
        {
            if(!pass[R[i][0]]){
                if(areteCourante[R[i][1]]==1){
                    listeCourante[u0+1].push_back(v0);
                    listeCourante[u0+1].push_back(v0+1);
                }else
                    listeCourante[u0+1].push_back(v0+pass[R[i][1]]);
            }else
            {
                if(areteCourante[R[i][1]]==1){
                    listeCourante[u0].push_back(v0);
                    listeCourante[u0].push_back(v0+1);
                }else
                    listeCourante[u0].push_back(v0+pass[R[i][1]]);
            }
        }
        pass[R[i][0]]++;
        pass[R[i][1]]++;
    }
    queue<int> f;
    f.push(2*P);
    d0[2*P]=1;
    int c0=-1;
    while(!f.empty())
    {
        int u=f.front();
        f.pop();
        for(int v:listeCourante[u])
        {
            if(!d0[v])
            {
                d0[v]= d0[u]+1;
                f.push(v);
            }else
            {
                c0=d0[u];
            }
        }
    }
    f.push(2*P+1);
    d1[2*P+1]=1;
    int c1=-1;
    while(!f.empty())
    {
        int u=f.front();
        f.pop();
        for(int v:listeCourante[u])
        {
            if(!d1[v])
            {

                d1[v]= d1[u]+1;
                f.push(v);
            }else
            {
                c1=d1[u];
            }
        }
    }

    for(int i=0;i<=2*N;i++){
        d0[i]--,d1[i]--;
    }
    for(int j=0;j<Q;j++)
    {
        int rs=0;
        for(int i=0;i<N;i++)
        {
            if(G[j]==d0[2*i] || G[j]==d1[2*i]){
                rs++;
            }
            else if(d0[2*i]!=-1 && c0!=-1 && G[j]>=d0[2*i] &&(G[j]-d0[2*i])%c0==0){
                rs++;
            }
            else if(d1[2*i]!=-1 && c1!=-1 && G[j]>=d1[2*i] && (G[j]-d1[2*i])%c1==0){
                rs++;
            }
        }
        answer(rs);
    }

}

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