oj.uz

Submission #29496

# Submission time Handle Problem Language Result Execution time Memory
29496 2017-07-19T13:52:39 Z osmanorhan Tropical Garden (IOI11_garden) C++14
0 / 100
 13 ms 11076 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11076 KB Output is correct
2 Correct 12 ms 11000 KB Output is correct
3 Correct 12 ms 10972 KB Output is correct
4 Correct 12 ms 10948 KB Output is correct
5 Incorrect 12 ms 10988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11076 KB Output is correct
2 Correct 12 ms 11000 KB Output is correct
3 Correct 12 ms 10972 KB Output is correct
4 Correct 12 ms 10948 KB Output is correct
5 Incorrect 12 ms 10988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11076 KB Output is correct
2 Correct 12 ms 11000 KB Output is correct
3 Correct 12 ms 10972 KB Output is correct
4 Correct 12 ms 10948 KB Output is correct
5 Incorrect 12 ms 10988 KB Output isn't correct
6 Halted 0 ms 0 KB -