Submission #776851

#	Time	Username	Problem	Language	Result	Execution time	Memory
776851		I_Love_EliskaM_	Tropical Garden (IOI11_garden)	C++14	69 / 100	5059 ms	83376 KiB

garden

#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()

bool foo(pi a, pi b) {
  return a.s < b.s;
}

const int _N=2e5;
const int K=30;
int up[2][_N][K];
int z[2][_N][K];
vector<pi> adj[_N];

pi jump(int u, int x, int f) {
  int from=f;
  for (int j=0; (1<<j)<=x; ++j) {
    if ((x>>j)&1) {
      if (from==adj[u][0].f) {
        from=z[1][u][j];
        u=up[1][u][j];
      } else {
        from=z[0][u][j];
        u=up[0][u][j];
      } 
    } 
  }
  return {u,from};
}

void count_routes(int n, int m, int p, int r[][2], int q, int *g) {
  
  forn(i,m) {
    int u=r[i][0], v=r[i][1];
    adj[u].pb({v,i});
    adj[v].pb({u,i});
  }
  forn(i,n) sort(all(adj[i]),foo);

  forn(i,n) {
    if (adj[i].size()>1) {
      up[0][i][0]=adj[i][0].f;
      up[1][i][0]=adj[i][1].f;
    } else {
      up[0][i][0]=up[1][i][0]=adj[i][0].f;
    }
    z[0][i][0]=z[1][i][0]=i;
  }
  for (int j=1; j<K; ++j) {
    forn(i,n) {
      forn(c,2) {
        int u=i, v=up[c][i][j-1];
        if (z[c][i][j-1]==adj[v][0].f) {
          up[c][i][j] = up[1][v][j-1];
          z[c][i][j] = z[1][v][j-1];
        } else {
          up[c][i][j] = up[0][v][j-1];
          z[c][i][j] = z[0][v][j-1];
        }
      }
    }
  }

  vector<pi> v; forn(i,q) v.pb({g[i],i});
  sort(all(v));
  map<int,int> mem;
  vector<int> ans(q);
  int last=0;
  vector<int> f(n); forn(i,n) f[i]=i;
  vector<int> s(n,-1);
  forn(i,q) {
    int k=v[i].f;
    if (mem[k]) {
      ans[v[i].s]=mem[k]-1; continue;
    }
    int z=0;
    forn(j,n) {
      auto it=jump(f[j],k-last,s[j]);
      f[j]=it.f, s[j]=it.s;
      z+=f[j]==p;
    }
    mem[k]=z+1;
    ans[v[i].s]=z;
    last=k;
  }
  forn(i,q) answer(ans[i]);
  
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:58:13: warning: unused variable 'u' [-Wunused-variable]
   58 |         int u=i, v=up[c][i][j-1];
      |             ^

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