Submission #122967

#	Time	Username	Problem	Language	Result	Execution time	Memory
122967		CaroLinda	Tropical Garden (IOI11_garden)	C++17	100 / 100	2902 ms	20932 KiB

garden

#include <bits/stdc++.h>
#include "gardenlib.h"
#include "garden.h"

#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back

const int MAXN = 15e4+10;
const int MAXM = 15e4+10 ;
const int MAXQ = 2005 ;
const int inf=0x3f3f3f3f ;

using namespace std;

int p ;
int graph[MAXN*2] ;
vector<int> v[MAXN] ;

bool marc[MAXN*2][2] ;
int checking,d[MAXN*2][2] ;

void dfs(int x, int y)
{
    if(marc[x][y]) return ;
    marc[x][y] = 1 ;
    dfs(graph[x],y) ;
    if(x!=2*p+y)
    d[x][y] = d[graph[x]][y]+1 ;
}

bool mod(int x, int y , int z)
{
    if( y == inf || x<y || (x-y)%z!=0 ) return false ;
    return true ;
}

void count_routes(int n, int m, int P, int r[][2], int q, int g[])
{
    p=P ;

    lp(i,0,m)
    lp(j,0,2)
    v[ r[i][j] ].pb(r[i][!j]) ;

    lp(i,0,n)
    if(v[i].size() == 1) v[i].pb(v[i][0]) ;

    lp(i,0,n)
    if(v[i].size() != 0)
    {
        if( i == v[v[i][0]][0] )
            graph[2*i] = 2*v[i][0]+1 ;
        else graph[2*i]=2*v[i][0] ;
        if( i == v[v[i][1]][0] )
            graph[2*i+1]=2*v[i][1]+1 ;
        else graph[2*i+1]=2*v[i][1];
    }

    lp(i,0,MAXN*2) d[i][0] = d[i][1]=inf ;
    lp(i,0,2) d[2*p+i][i] = 0 ;
    lp(i,0,2) dfs(2*p+i, i) ;
    lp(i,0,2*n) dfs(i,0) , dfs(i,1) ;

   int cycle[2] = { d[graph[2*p]][0]+1, d[graph[2*p+1]][1]+1 } ;

   lp(i,0,q)
   {
       int ans =0  ;
       for(int j = 0 ; j<2*n ; j+=2)
        if(mod(g[i],d[j][0],cycle[0]) || mod(g[i],d[j][1],cycle[1])) ans ++ ;
        answer(ans) ;
   }

}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:72:8: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
        for(int j = 0 ; j<2*n ; j+=2)
        ^~~
garden.cpp:74:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         answer(ans) ;
         ^~~~~~

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