Submission #29496

#	Time	Username	Problem	Language	Result	Execution time	Memory
29496		osmanorhan	Tropical Garden (IOI11_garden)	C++14	0 / 100	13 ms	11076 KiB

garden

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

using namespace std;

const int maxn = 150020;

typedef pair<int,int> ii;

vector<int> best[maxn];
vector<ii> w[maxn][2];

int mark[maxn], went[maxn], cycle;
int ans[maxn], p;

void dfs( int n, int s, int deep ) {
    if( n == p && deep != 0 ) {
        cycle = deep;
        return;
    }

    if( s == 0 ) mark[n] = deep, went[n] = 1;

    for(int i=0;i<w[n][s].size();i++)
        dfs( w[n][s][i].first, w[n][s][i].second, deep+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++) {
        int u = R[i][0];
        int v = R[i][1];
        if( best[v].size() <= 1 ) best[v].pb( u );
        if( best[u].size() <= 1 ) best[u].pb( v );
    }
    for(int i=0;i<N;i++)
        if( best[i].size() == 1 ) best[i].pb( best[i][0] );

    for(int i=0;i<N;i++)
        for(int j=0;j<2;j++) {
            int go = best[i][j];
            int s = (best[go][0] == i);
            w[go][s].pb( ii( i, j ) );
        }

    for(int l=0;l<2;l++) {
        for(int i=0;i<N;i++) mark[i] = went[i] = 0;
        cycle = -1;
        dfs( P, l, 0 );
        for(int i=0;i<N;i++) {
            if( !went[i] ) continue;
            for(int j=0;j<Q;j++) {
                if( mark[i] > G[j] ) continue;
                if( cycle == -1 && G[j] == mark[i] ) ans[j]++;
                else if( cycle > 0 && (G[j]-mark[i])%cycle == 0 ) ans[j]++;
            }
        }
    }

    for(int i=0;i<Q;i++)
        answer( ans[i] );

}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<w[n][s].size();i++)
                 ~^~~~~~~~~~~~~~~

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