Submission #583096

#	Time	Username	Problem	Language	Result	Execution time	Memory
583096		gustavoleal	Tropical Garden (IOI11_garden)	C++17	100 / 100	2706 ms	25804 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31