Submission #36271

#	Time	Username	Problem	Language	Result	Execution time	Memory
36271		funcsr	Tropical Garden (IOI11_garden)	C++14	100 / 100	203 ms	32212 KiB

garden

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define INF 1145141919
#define rep(i, n) for (int i=0; i<(n); i++)
#define _1 first
#define _2 second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef pair<int, int> P;
int N, M, T, Q;
vector<P> G[150000];
vector<int> G2[150000*2];
int F[150000*2];
int A[2000];
int D[150000*2];
int C[2][150000*2];

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

int bfs(int s) {
  queue<int> q;
  rep(i, 2*N) D[i] = INF;
  D[s] = 0;
  q.push(s);
  int ret = INF;
  while (!q.empty()) {
    int x = q.front(); q.pop();
    for (int t : G2[x]) {
      if (t == s) ret = min(ret, D[x]+1);
      if (D[t] > D[x]+1) {
        D[t] = D[x]+1;
        q.push(t);
      }
    }
  }
  return ret;
}

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, 2*N) G2[i].clear();
  rep(i, N) {
    F[i] = fg(G[i][0]);
    F[i+N] = fg((G[i].size()>=2)? G[i][1] : G[i][0]);
  }
  rep(i, 2*N) G2[F[i]].pb(i);
  vector<int> S[2];
  int r[2];
  r[0] = bfs(T  ); rep(i, N) S[0].pb(D[i]); sort(all(S[0]), greater<int>());
  r[1] = bfs(T+N); rep(i, N) S[1].pb(D[i]); sort(all(S[1]), greater<int>());
  rep(i, 2) rep(t, 2*N) C[i][t] = 0;

  vector<P> qs;
  rep(i, Q) qs.pb(P(g[i], i));
  sort(all(qs));

  rep(_, Q) {
    int k = qs[_]._1, q = qs[_]._2;
    int ctr = 0;
    rep(i, 2) {
      while (!S[i].empty() && S[i].back() <= k) {
        int t = S[i].back();
        if (r[i] != INF) C[i][t%r[i]]++;
        else if (t == k) ctr++;
        S[i].pop_back();
      }
    }
    rep(i, 2) if (r[i] != INF) ctr += C[i][k%r[i]];
    A[q] = ctr;
  }
  rep(i, Q) answer(A[i]);
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31