Submission #776993

#	Time	Username	Problem	Language	Result	Execution time	Memory
776993		I_Love_EliskaM_	Tropical Garden (IOI11_garden)	C++14	100 / 100	2233 ms	59852 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;
}

struct DSU {
  vector<int> p,sz;
  DSU(int n) {
    forn(i,n) p.pb(i), sz.pb(1);
  }
  int get(int u) {
    return p[u]==u?u:get(p[u]);
  }
  void uni(int u, int v) {
    u=get(u), v=get(v);
    if (u==v) return;
    if (sz[u]<sz[v]) swap(u,v);
    p[v]=u;
    sz[u]+=sz[v];
  }
};

const int N=4e5;
const int K=20;
int up[N][K];
vector<pi> adj[N];
int to[N+5];
int in[N+5];
int d[N+5];
int vis[N+5];
int iscyc[N+5];
DSU dsu(N);
int dist[N], dist2[N];
int mod[N], mod2[N];
int sz[N];

int cyc=0, pt=-1;

void dfs(int u) {
  if (vis[u]==1) {
    cyc=1;
    pt=u;
    d[u]=0;
    return;
  }
  if (vis[u]==2) return;
  vis[u]=1;
  dfs(to[u]);
  dsu.uni(u,to[u]);
  vis[u]=2;
  d[u]=d[to[u]]+1;
  iscyc[u]=cyc;
  if (cyc) sz[dsu.get(u)]=max(sz[dsu.get(u)],d[u]);
  if (u==pt) {
    cyc=0;
    pt=-1;
  }
}

int jump(int u, int x) {
  for (int j=K-1; j>=0; --j) {
    if ((x>>j)&1) {
      u=up[u][j];
    }
  }
  return u;
}

void count_routes(int n, int m, int p, int r[][2], int q, int *g) {

  forn(i,N+5) to[i]=i;

  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) {
    int v=adj[i][0].f;
    if (adj[v].size()==1) {
      to[i]=v;
    } else {
      if (i==adj[v][0].f) {
        to[i]=v+n;
      } else {
        to[i]=v;
      }
    }

    if (adj[i].size()>1) {
      v=adj[i][1].f;
      if (adj[v].size()==1) {
        to[i+n]=v;
      } else {
        if (i==adj[v][0].f) {
          to[i+n]=v+n;
        } else {
          to[i+n]=v;
        }
      }
    }
  }

  forn(i,2*n) up[i][0]=to[i];
  for (int j=1;j<K;++j) {
    forn(i,2*n) up[i][j]=up[up[i][j-1]][j-1];
  }

  forn(i,n) in[to[i]]++, in[to[i+n]]++;
  forn(i,n) {
    if (!in[i]) dfs(i);
    if (!in[i+n]) dfs(i);
  }
  forn(i,2*n) if (!vis[i]) dfs(i);

  //forn(i,2*n) cout<<i<<"->"<<to[i]<<'\n';
  //// 0->1->2->7->6->9->10->11->1
  //// 0->6->7->8->1->0
  //// 3->2->1 4->2->1
  //// 8=1 7=2 6=3 0=4 1=5 2=6 3=7 4=7
  //forn(i,2*n) cout<<vis[i]<<' '<<d[i]<<' '<<iscyc[i]<<' '<<dsu.get(i)<<' '<<sz[dsu.get(i)]<<'\n';
  //return;
  
  forn(i,n) {
    mod[i]=mod2[i]=-1;
    if (dsu.get(i)==dsu.get(p)) {
      if (iscyc[p]) {
        mod[i]=sz[dsu.get(p)];
        dist[i]=(d[i]-d[p]);
        if (dist[i]<0) dist[i]+=mod[i];
      } else {
        if (d[i] >= d[p]) {
          int u=jump(i,d[i]-d[p]);
          if (u==p) {
            dist[i] = d[i]-d[p];
          }
        }
      }
    }
    p+=n;
    if (dsu.get(i)==dsu.get(p)) {
      if (iscyc[p]) {
        mod2[i]=sz[dsu.get(p)];
        dist2[i]=(d[i]-d[p]);
        if (dist2[i]<0) dist2[i]+=mod2[i];
      } else {
        if (d[i] >= d[p]) {
          int u=jump(i,d[i]-d[p]);
          if (u==p) {
            dist2[i] = d[i]-d[p];
          }
        }
      }
    }
    p-=n;
  }
  //forn(i,n) cout<<mod[i]<<' '<<dist[i]<<' '<<mod2[i]<<' '<<dist2[i]<<'\n';

  forn(j,q) {
    int k=g[j];
    int ans=0;
    forn(i,n) {
      int z=0;
      if (mod[i]==-1) {
        z|=dist[i]==k;
      } else {
        if (k>=dist[i]) z|=(k-dist[i])%mod[i] == 0;
      }
      if (mod2[i]==-1) {
        z|=dist2[i]==k;
      } else {
        if (k>=dist2[i]) z|=(k-dist2[i])%mod2[i] == 0;
      }
      ans+=z;
    }
    answer(ans);
  }

}

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