Submission #36267

#	Time	Username	Problem	Language	Result	Execution time	Memory
36267		funcsr	Tropical Garden (IOI11_garden)	C++14	0 / 100	6 ms	4192 KiB

garden

#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) {
    sort(all(G[i]));
    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, 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: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31