oj.uz

Submission #36268

# Submission time Handle Problem Language Result Execution time Memory
36268 2017-12-07T03:09:14 Z funcsr Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 46568 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define _1 first
#define all(x) x.begin(), x.end()
#define _2 second
#define pb push_back
typedef pair<int, int> P;
int N, M, T, Q;
vector<P> G[150000];
int best[150000];
int F[30][150000*2];

inline int fg(P p) {
  int x = p._2, e = p._1;
  if (best[x] == e) return x+N;
  else return x;
}

inline int go(int x, int s) {
  for (int k=29; k>=0; k--) if ((s>>k)&1) x = F[k][x];
  return x;
}

void count_routes(int n, int m, int p, int edges[][2], int q, int g[]) {
  N = n, M = m, T = p, Q = q;
  rep(i, N) G[i].clear();
  rep(i, M) {
    G[edges[i][0]].pb(P(i, edges[i][1]));
    G[edges[i][1]].pb(P(i, edges[i][0]));
  }
  rep(i, N) best[i] = G[i][0]._1;
  rep(i, N) {
    F[0][i] = fg(G[i][0]);
    F[0][i+N] = fg((G[i].size()>=2)? G[i][1] : G[i][0]);
  }
  rep(k, 29) rep(i, 2*N) F[k+1][i] = F[k][F[k][i]];
  rep(i, Q) {
    int k = g[i];
    int ctr = 0;
    rep(x, N) {
      int v = go(x, k);
      if (v == T || v == T+N) ctr++;
    }
    answer(ctr);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4308 KB Output is correct
2 Correct 6 ms 4316 KB Output is correct
3 Correct 6 ms 4316 KB Output is correct
4 Correct 5 ms 4088 KB Output is correct
5 Correct 5 ms 4088 KB Output is correct
6 Correct 6 ms 4316 KB Output is correct
7 Correct 5 ms 4088 KB Output is correct
8 Correct 6 ms 4344 KB Output is correct
9 Correct 8 ms 4568 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4308 KB Output is correct
2 Correct 6 ms 4316 KB Output is correct
3 Correct 6 ms 4316 KB Output is correct
4 Correct 5 ms 4088 KB Output is correct
5 Correct 5 ms 4088 KB Output is correct
6 Correct 6 ms 4316 KB Output is correct
7 Correct 5 ms 4088 KB Output is correct
8 Correct 6 ms 4344 KB Output is correct
9 Correct 8 ms 4568 KB Output is correct
10 Correct 5 ms 4060 KB Output is correct
11 Correct 21 ms 10332 KB Output is correct
12 Correct 39 ms 15252 KB Output is correct
13 Correct 57 ms 27640 KB Output is correct
14 Correct 119 ms 42600 KB Output is correct
15 Correct 126 ms 43232 KB Output is correct
16 Correct 106 ms 31740 KB Output is correct
17 Correct 98 ms 28056 KB Output is correct
18 Correct 41 ms 15356 KB Output is correct
19 Correct 117 ms 42972 KB Output is correct
20 Correct 125 ms 43604 KB Output is correct
21 Correct 108 ms 32016 KB Output is correct
22 Correct 100 ms 27824 KB Output is correct
23 Correct 139 ms 46568 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4308 KB Output is correct
2 Correct 6 ms 4316 KB Output is correct
3 Correct 6 ms 4316 KB Output is correct
4 Correct 5 ms 4088 KB Output is correct
5 Correct 5 ms 4088 KB Output is correct
6 Correct 6 ms 4316 KB Output is correct
7 Correct 5 ms 4088 KB Output is correct
8 Correct 6 ms 4344 KB Output is correct
9 Correct 8 ms 4568 KB Output is correct
10 Correct 5 ms 4060 KB Output is correct
11 Correct 21 ms 10332 KB Output is correct
12 Correct 39 ms 15252 KB Output is correct
13 Correct 57 ms 27640 KB Output is correct
14 Correct 119 ms 42600 KB Output is correct
15 Correct 126 ms 43232 KB Output is correct
16 Correct 106 ms 31740 KB Output is correct
17 Correct 98 ms 28056 KB Output is correct
18 Correct 41 ms 15356 KB Output is correct
19 Correct 117 ms 42972 KB Output is correct
20 Correct 125 ms 43604 KB Output is correct
21 Correct 108 ms 32016 KB Output is correct
22 Correct 100 ms 27824 KB Output is correct
23 Correct 139 ms 46568 KB Output is correct
24 Correct 14 ms 4088 KB Output is correct
25 Correct 3117 ms 10460 KB Output is correct
26 Correct 4676 ms 15428 KB Output is correct
27 Execution timed out 5008 ms 27988 KB Time limit exceeded
28 Halted 0 ms 0 KB -