oj.uz

Submission #241547

# Submission time Handle Problem Language Result Execution time Memory
241547 2020-06-24T12:09:17 Z Andrei_Cotor Tropical Garden (IOI11_garden) C++11
49 / 100
 61 ms 10488 KB 
#include"garden.h"
#include"gardenlib.h"
#include<vector>
#include<algorithm>
#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];

void getDist(int nod)
{
    Viz[nod]=1;

    if(!Viz[Exit[nod]])
        getDist(Exit[nod]);

    Dist[nod]=1+Dist[Exit[nod]];
}

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++;
        }

        Sol[Qry[i].second]+=Fr[Qry[i].first%cycleSize];
    }
}

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 6 ms 1536 KB Output is correct
7 Correct 6 ms 1536 KB Output is correct
8 Correct 6 ms 1536 KB Output is correct
9 Correct 8 ms 1664 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 6 ms 1536 KB Output is correct
7 Correct 6 ms 1536 KB Output is correct
8 Correct 6 ms 1536 KB Output is correct
9 Correct 8 ms 1664 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 16 ms 2560 KB Output is correct
12 Correct 25 ms 3456 KB Output is correct
13 Correct 41 ms 8056 KB Output is correct
14 Correct 60 ms 7672 KB Output is correct
15 Correct 61 ms 7800 KB Output is correct
16 Correct 58 ms 6392 KB Output is correct
17 Runtime error 53 ms 10488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 6 ms 1536 KB Output is correct
7 Correct 6 ms 1536 KB Output is correct
8 Correct 6 ms 1536 KB Output is correct
9 Correct 8 ms 1664 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 16 ms 2560 KB Output is correct
12 Correct 25 ms 3456 KB Output is correct
13 Correct 41 ms 8056 KB Output is correct
14 Correct 60 ms 7672 KB Output is correct
15 Correct 61 ms 7800 KB Output is correct
16 Correct 58 ms 6392 KB Output is correct
17 Runtime error 53 ms 10488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -