oj.uz

Submission #583096

# Submission time Handle Problem Language Result Execution time Memory
583096 2022-06-24T20:36:09 Z gustavoleal Tropical Garden (IOI11_garden) C++17
100 / 100
 2706 ms 25804 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=400100;
typedef long long ll;

vector<int> lista[N];
int pass[N],grau[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++)
        grau[R[i][0]]++,grau[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(grau[R[i][0]]==1){
                    lista[v0+1].push_back(u0);
                    lista[v0+1].push_back(u0+1);
                }else
                    lista[v0+1].push_back(u0+pass[R[i][0]]);
            }else
            {

                if(grau[R[i][0]]==1){
                    lista[v0].push_back(u0);
                    lista[v0].push_back(u0+1);
                }else
                    lista[v0].push_back(u0+pass[R[i][0]]);
            }
            
        }
        if(pass[R[i][1]]<=1)
        {
            if(!pass[R[i][0]]){
                if(grau[R[i][1]]==1){
                    lista[u0+1].push_back(v0);
                    lista[u0+1].push_back(v0+1);
                }else
                    lista[u0+1].push_back(v0+pass[R[i][1]]);
            }else
            {
                if(grau[R[i][1]]==1){
                    lista[u0].push_back(v0);
                    lista[u0].push_back(v0+1);
                }else
                    lista[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:lista[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:lista[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]--;
        // if(i%2==0)
            // cout<<d1[i]<<"<\n";
    }
    // cout<<c0<<" "<<c1<<'\n';
    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]){
                // cout<<i<<" "<<d0[2*i]<<" "<<d1[2*i]<<"\n";
                rs++;
            }
            else if(d0[2*i]!=-1 && c0!=-1 && G[j]>=d0[2*i] &&(G[j]-d0[2*i])%c0==0){
                // cout<<i<<"<\n";
                rs++;
            }
            else if(d1[2*i]!=-1 && c1!=-1 && G[j]>=d1[2*i] && (G[j]-d1[2*i])%c1==0){
                // cout<<i<<"<<\n";
                rs++;
            }
        }
        answer(rs);
    }
    
}

// void answer(int X)
// {
//     cout<<X<<"\n";
// }
// int n, M,P, R[100][2], Q, G[100];
// int main()
// {
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     cin>>n>>M>>P>>Q;
//     for(int i=0;i<M;i++)
//         cin>>R[i][0]>>R[i][1];
//     for(int i=0;i<Q;i++)
//         cin>>G[i];
    
//     count_routes(n,M,P,R,Q,G);

//     return 0;
// }

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 7 ms 9784 KB Output is correct
3 Correct 7 ms 9848 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 8 ms 9848 KB Output is correct
7 Correct 7 ms 9720 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 7 ms 9896 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 7 ms 9784 KB Output is correct
3 Correct 7 ms 9848 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 8 ms 9848 KB Output is correct
7 Correct 7 ms 9720 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 7 ms 9896 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 13 ms 11628 KB Output is correct
12 Correct 31 ms 12900 KB Output is correct
13 Correct 38 ms 18612 KB Output is correct
14 Correct 83 ms 20144 KB Output is correct
15 Correct 93 ms 20488 KB Output is correct
16 Correct 66 ms 17760 KB Output is correct
17 Correct 64 ms 17072 KB Output is correct
18 Correct 23 ms 12916 KB Output is correct
19 Correct 74 ms 20188 KB Output is correct
20 Correct 102 ms 20456 KB Output is correct
21 Correct 68 ms 17768 KB Output is correct
22 Correct 64 ms 16964 KB Output is correct
23 Correct 65 ms 21080 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 7 ms 9784 KB Output is correct
3 Correct 7 ms 9848 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 8 ms 9848 KB Output is correct
7 Correct 7 ms 9720 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 7 ms 9896 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 13 ms 11628 KB Output is correct
12 Correct 31 ms 12900 KB Output is correct
13 Correct 38 ms 18612 KB Output is correct
14 Correct 83 ms 20144 KB Output is correct
15 Correct 93 ms 20488 KB Output is correct
16 Correct 66 ms 17760 KB Output is correct
17 Correct 64 ms 17072 KB Output is correct
18 Correct 23 ms 12916 KB Output is correct
19 Correct 74 ms 20188 KB Output is correct
20 Correct 102 ms 20456 KB Output is correct
21 Correct 68 ms 17768 KB Output is correct
22 Correct 64 ms 16964 KB Output is correct
23 Correct 65 ms 21080 KB Output is correct
24 Correct 7 ms 9684 KB Output is correct
25 Correct 132 ms 11636 KB Output is correct
26 Correct 149 ms 12988 KB Output is correct
27 Correct 2275 ms 18720 KB Output is correct
28 Correct 1174 ms 20272 KB Output is correct
29 Correct 2706 ms 20588 KB Output is correct
30 Correct 1505 ms 17872 KB Output is correct
31 Correct 1430 ms 17232 KB Output is correct
32 Correct 164 ms 12992 KB Output is correct
33 Correct 1163 ms 20256 KB Output is correct
34 Correct 2632 ms 20560 KB Output is correct
35 Correct 1517 ms 17904 KB Output is correct
36 Correct 1728 ms 17112 KB Output is correct
37 Correct 823 ms 21184 KB Output is correct
38 Correct 2608 ms 25804 KB Output is correct