Submission #60793

#	Time	Username	Problem	Language	Result	Execution time	Memory
60793		Vahan	Tropical Garden (IOI11_garden)	C++17	100 / 100	2871 ms	46232 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<vector>
#include<iostream>
using namespace std;
int p,u[400000],u1[400000],u2[400000],l1[400000],l2[400000];
int a[400000];
const int MAXN=400000;
vector<int> g[400005],inv[400000];
int dfs1(int v)
{
    if(v==2*p)
        return 1;
    if(u[v]==1)
        return -MAXN;
    u[v]=1;
    return dfs1(a[v])+1;
}
int dfs2(int v)
{
    if(v==2*p+1)
        return 1;
    if(u[v]==1)
        return -MAXN;
    u[v]=1;
    return dfs2(a[v])+1;
}
void dfs11(int v,int h)
{
    if(u1[v]==1)
        return;
    u1[v]=1;
    l1[v]=h;
    for(int i=0;i<inv[v].size();i++)
    {
        int to=inv[v][i];
        dfs11(to,h+1);
    }
}
void dfs22(int v,int h)
{
    if(u2[v]==1)
        return;
    u2[v]=1;
    l2[v]=h;
    for(int i=0;i<inv[v].size();i++)
    {
        int to=inv[v][i];
        dfs22(to,h+1);
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    p=P;
    for(int i=0;i<M;i++)
    {
        g[R[i][0]].push_back(R[i][1]);
        g[R[i][1]].push_back(R[i][0]);
    }
    for(int i=0;i<N;i++)
    {
        if(g[i].size()==1)
        {
            if(g[g[i][0]][0]==i)
                a[2*i+1]=2*g[i][0]+1;
            else
                a[2*i+1]=2*g[i][0];
                a[2*i]=a[2*i+1];
        }
        else
        {
            if(g[g[i][0]][0]==i)
                a[2*i]=2*g[i][0]+1;
            else
                a[2*i]=2*g[i][0];
            if(g[g[i][1]][0]==i)
                a[2*i+1]=2*g[i][1]+1;
            else
                a[2*i+1]=2*g[i][1];
        }
    }
    for(int i=0;i<2*N;i++)
    {
        inv[a[i]].push_back(i);
        l1[i]=-1;
        l2[i]=-1;
    }
    int r1=dfs1(a[2*P]);
    if(r1<0)
        r1=0;
    for(int i=0;i<2*N;i++)
        u[i]=0;
    int r2=dfs2(a[2*P+1]);
    if(r2<0)
        r2=0;
    dfs11(2*p,0);
    dfs22(2*p+1,0);
    for(int i=0;i<Q;i++)
    {
        int an=0;
        for(int j=0;j<N;j++)
        {
            if(r1==0 && G[i]==l1[2*j])
                an++;
            else if(r1>0 && G[i]-l1[2*j]>=0 && (G[i]-l1[2*j])%r1==0 && l1[2*j]!=-1)
                an++;
            else if(r2==0 && G[i]==l2[2*j])
                an++;
            else if(r2>0 && G[i]-l2[2*j]>=0 && (G[i]-l2[2*j])%r2==0 && l2[2*j]!=-1)
                an++;
        }
        answer(an);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void dfs11(int, int)':
garden.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<inv[v].size();i++)
                 ~^~~~~~~~~~~~~~
garden.cpp: In function 'void dfs22(int, int)':
garden.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<inv[v].size();i++)
                 ~^~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:66:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
             else
             ^~~~
garden.cpp:68:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
                 a[2*i]=a[2*i+1];
                 ^

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