oj.uz

Submission #16991

# Submission time Handle Problem Language Result Execution time Memory
16991 2015-11-03T16:49:02 Z murat Tropical Garden (IOI11_garden) C++
100 / 100
 1438 ms 47488 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 3e5 + 5;

int T, p, sz, n, m, x, y, S, t, k, h[N][2];
vector< int > v[N];
vector< pii > g[N][2];
pii D[N], GG[N];

void dfs(int node, int w, int ww, int s, pii rt) {
    if(node == p && w == ww && s) { sz = s; return ; }
    if(!w) D[++S] = mp(0, s);
    foreach(it, g[node][w])
        dfs(it->st, it->nd, ww, s + 1, mp(node, w));
}

int take(int k) {
    int ans = 0;
    FOR(i, 1, S) {
        if(k >= D[i].nd && (k - D[i].nd) % D[i].st == 0)
            ans++;
    }
    return ans;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i; p = P;

    n = N, m = M;

    FOR(i, 0, m-1) {
        int x = R[i][0], y = R[i][1];
        if(v[x].size() < 2) v[x].pb(y);
        if(v[y].size() < 2) v[y].pb(x);
    }

    FOR(i, 0, n-1)
        FOR(j, 0, (int)v[i].size()-1) {
            pii y = mp(i, j);
            pii x = mp(v[i][j], 0);
            if(v[v[i][j]][0] == i && v[v[i][j]].size() > 1) x.nd = 1;
            g[x.st][x.nd].pb(y);
        }

    sz = inf + 10; dfs(p, 0, 0, 0, mp(0, 0));
    FOR(i, 1, S) D[i].st = sz; int t = S + 1;
    sz = inf + 10; dfs(p, 1, 1, 0, mp(0, 0));
    FOR(i, t, S) D[i].st = sz;

    for(i=0; i<Q; i++)
        answer(take(G[i]));
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:11:23: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
                       ^
garden.cpp:80:5: note: in expansion of macro 'FOR'
     FOR(i, 1, S) D[i].st = sz; int t = S + 1;
     ^~~
garden.cpp:80:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     FOR(i, 1, S) D[i].st = sz; int t = S + 1;
                                ^~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21680 KB Output is correct
2 Correct 22 ms 21624 KB Output is correct
3 Correct 23 ms 21676 KB Output is correct
4 Correct 22 ms 21500 KB Output is correct
5 Correct 22 ms 21468 KB Output is correct
6 Correct 22 ms 21752 KB Output is correct
7 Correct 23 ms 21552 KB Output is correct
8 Correct 22 ms 21624 KB Output is correct
9 Correct 24 ms 21656 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21680 KB Output is correct
2 Correct 22 ms 21624 KB Output is correct
3 Correct 23 ms 21676 KB Output is correct
4 Correct 22 ms 21500 KB Output is correct
5 Correct 22 ms 21468 KB Output is correct
6 Correct 22 ms 21752 KB Output is correct
7 Correct 23 ms 21552 KB Output is correct
8 Correct 22 ms 21624 KB Output is correct
9 Correct 24 ms 21656 KB Output is correct
10 Correct 21 ms 21496 KB Output is correct
11 Correct 34 ms 23612 KB Output is correct
12 Correct 58 ms 24892 KB Output is correct
13 Correct 85 ms 42612 KB Output is correct
14 Correct 181 ms 32284 KB Output is correct
15 Correct 240 ms 33456 KB Output is correct
16 Correct 162 ms 30520 KB Output is correct
17 Correct 142 ms 29224 KB Output is correct
18 Correct 58 ms 24896 KB Output is correct
19 Correct 168 ms 32220 KB Output is correct
20 Correct 195 ms 33456 KB Output is correct
21 Correct 157 ms 30324 KB Output is correct
22 Correct 139 ms 29160 KB Output is correct
23 Correct 170 ms 33292 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21680 KB Output is correct
2 Correct 22 ms 21624 KB Output is correct
3 Correct 23 ms 21676 KB Output is correct
4 Correct 22 ms 21500 KB Output is correct
5 Correct 22 ms 21468 KB Output is correct
6 Correct 22 ms 21752 KB Output is correct
7 Correct 23 ms 21552 KB Output is correct
8 Correct 22 ms 21624 KB Output is correct
9 Correct 24 ms 21656 KB Output is correct
10 Correct 21 ms 21496 KB Output is correct
11 Correct 34 ms 23612 KB Output is correct
12 Correct 58 ms 24892 KB Output is correct
13 Correct 85 ms 42612 KB Output is correct
14 Correct 181 ms 32284 KB Output is correct
15 Correct 240 ms 33456 KB Output is correct
16 Correct 162 ms 30520 KB Output is correct
17 Correct 142 ms 29224 KB Output is correct
18 Correct 58 ms 24896 KB Output is correct
19 Correct 168 ms 32220 KB Output is correct
20 Correct 195 ms 33456 KB Output is correct
21 Correct 157 ms 30324 KB Output is correct
22 Correct 139 ms 29160 KB Output is correct
23 Correct 170 ms 33292 KB Output is correct
24 Correct 22 ms 21496 KB Output is correct
25 Correct 53 ms 23656 KB Output is correct
26 Correct 61 ms 24952 KB Output is correct
27 Correct 1438 ms 42228 KB Output is correct
28 Correct 356 ms 31852 KB Output is correct
29 Correct 1287 ms 32956 KB Output is correct
30 Correct 863 ms 30024 KB Output is correct
31 Correct 776 ms 28780 KB Output is correct
32 Correct 68 ms 25208 KB Output is correct
33 Correct 355 ms 32476 KB Output is correct
34 Correct 1282 ms 33580 KB Output is correct
35 Correct 877 ms 30644 KB Output is correct
36 Correct 977 ms 29640 KB Output is correct
37 Correct 277 ms 32764 KB Output is correct
38 Correct 1360 ms 47488 KB Output is correct