제출 #29501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29501		osmanorhan	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	1642 ms	32204 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, L;

void dfs( int n, int s, int deep ) {
    if( n == p && s == L && 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;
        L = l;
        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] );

}

컴파일 시 표준 에러 (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: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31