Submission #241602

#	Time	Username	Problem	Language	Result	Execution time	Memory
241602		Andrei_Cotor	Tropical Garden (IOI11_garden)	C++11	100 / 100	76 ms	9052 KiB

garden

#include"garden.h"
#include"gardenlib.h"
#include<vector>
#include<algorithm>
#include<deque>

#define INF 1000000000

using namespace std;

int Exit[300005]; //daca i<=N sunt in nodul i si ies prin cea mai mare muchie, i>N ies prin a doua cea mai mare
int Prim[150005],Sec[150005];
bool Viz[300005];
int Dist[300005];
int Sol[2005];

deque<int> Q;

void getDist(int nod)
{
    int cr=nod;
    while(!Viz[cr])
    {
        Viz[cr]=1;
        Q.push_back(cr);
        cr=Exit[cr];
    }

    while(!Q.empty())
    {
        Dist[Q.back()]=1+Dist[Exit[Q.back()]];
        Q.pop_back();
    }
}

pair<int,int> Qry[2005];
int Fr[300005];

void getSol(int N, int Q, int G[], int cycleSize)
{
    for(int i=0; i<=300000; i++)
        Fr[i]=0;
    for(int i=0; i<Q; i++)
        Qry[i+1]={G[i],i+1};

    sort(Qry+1,Qry+Q+1);
    sort(Dist+1,Dist+N+1);

    //Dist[nod]<=Qry[ind] si Dist[nod]%cycleSize==Qry[ind]%cycleSize ca sa pot ajunge in P si nod<=N (o sa ies prin cel mai mare edge)
    //daca cycleSize e INF, practic nu se face modulo, lungimile trb sa fie egale (P nu e in niciun ciclu)

    int j=1;
    for(int i=1; i<=Q; i++)
    {
        while(j<=N && Dist[j]<=Qry[i].first)
        {
            if(Dist[j]>=INF)
                continue;

            Fr[Dist[j]%cycleSize]++;
            j++;
        }

        if(cycleSize<INF)
            Sol[Qry[i].second]+=Fr[Qry[i].first%cycleSize];
        else if(Qry[i].first<=300000)
            Sol[Qry[i].second]+=Fr[Qry[i].first];
    }
}

void addEdge(int ind, int x, int y, int N)
{
    if(ind==Prim[x])
    {
        if(ind==Prim[y] && Sec[y])
            Exit[x]=N+y;
        else
            Exit[x]=y;
    }
    else if(ind==Sec[x])
    {
        if(ind==Prim[y] && Sec[y])
            Exit[N+x]=N+y;
        else
            Exit[N+x]=y;
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    for(int i=0; i<M; i++)
    {
        R[i][0]++;
        R[i][1]++;

        if(!Prim[R[i][0]])
            Prim[R[i][0]]=i+1;
        else if(!Sec[R[i][0]])
            Sec[R[i][0]]=i+1;

        if(!Prim[R[i][1]])
            Prim[R[i][1]]=i+1;
        else if(!Sec[R[i][1]])
            Sec[R[i][1]]=i+1;
    }

    for(int i=0; i<=M; i++)
    {
        addEdge(i+1,R[i][0],R[i][1],N);
        addEdge(i+1,R[i][1],R[i][0],N);
    }

    for(int i=1; i<=2*N; i++)
        Dist[i]=INF;

    P++;
    Dist[0]=INF;
    Viz[0]=1;
    //termin in nodul P

    Viz[P]=1;
    Dist[P]=0;
    for(int i=1; i<=2*N; i++)
    {
        if(!Viz[i])
            getDist(i);
    }

    int cycleSize=1+Dist[Exit[P]]; //dupa ce va ajunge in P va face ciclul respectiv, daca P se afla pe vreun ciclu
    getSol(N,Q,G,cycleSize);

    //termin in 2*P
    for(int i=1; i<=2*N; i++)
    {
        Dist[i]=INF;
        Viz[i]=0;
    }

    Viz[N+P]=1;
    Dist[N+P]=0;
    for(int i=1; i<=2*N; i++)
    {
        if(!Viz[i])
            getDist(i);
    }

    cycleSize=1+Dist[Exit[N+P]];
    getSol(N,Q,G,cycleSize);

    for(int i=1; i<=Q; i++)
        answer(Sol[i]);
}

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