oj.uz

Submission #241549

# Submission time Handle Problem Language Result Execution time Memory
241549 2020-06-24T12:17:11 Z Andrei_Cotor Tropical Garden (IOI11_garden) C++11
49 / 100
 65 ms 8952 KB 
#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++;
        }

        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 6 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 5 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 5 ms 1536 KB Output is correct
9 Correct 7 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 6 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 5 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 5 ms 1536 KB Output is correct
9 Correct 7 ms 1664 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 14 ms 2304 KB Output is correct
12 Correct 26 ms 2944 KB Output is correct
13 Correct 40 ms 5012 KB Output is correct
14 Correct 64 ms 6012 KB Output is correct
15 Correct 65 ms 6136 KB Output is correct
16 Correct 59 ms 4984 KB Output is correct
17 Runtime error 54 ms 8952 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 6 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 5 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 5 ms 1536 KB Output is correct
9 Correct 7 ms 1664 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 14 ms 2304 KB Output is correct
12 Correct 26 ms 2944 KB Output is correct
13 Correct 40 ms 5012 KB Output is correct
14 Correct 64 ms 6012 KB Output is correct
15 Correct 65 ms 6136 KB Output is correct
16 Correct 59 ms 4984 KB Output is correct
17 Runtime error 54 ms 8952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -