Submission #787550

#	Time	Username	Problem	Language	Result	Execution time	Memory
787550		Ronin13	Tropical Garden (IOI11_garden)	C++17	49 / 100	43 ms	27672 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 200001;
vector <vector <int> > g(nmax);
int nx[nmax];
int p[nmax];

vector <vector <int> > vv[2];

void bfs(int s, int ind, int n){
    int cnt = 0;
   
    queue <int> q;
    q.push(s);
    vector <bool> used(2 * n + 1);
    used[s] = true;
    fill(p, p + 2 * n, -1);
    p[s] = -1;
    int cyc = s;
    bool rrr = false;
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int to : g[v]){
          if(used[to]){
            cyc = v;rrr = true;
            break;
          }
          else p[to] = v, q.push(to), used[to] = true;
        }
        if(rrr) break;
    }
    
    while(cyc != -1){
      cnt++;
      cyc = p[cyc];
    }
    vv[ind].resize(cnt);
    while(!q.empty())q.pop();
    used.assign(2 * n + 1, false);
    vector <int> depth(2 * n + 1, -1);
    depth[s] = 0;
    q.push(s);
    while(!q.empty()){
      int v = q.front(); q.pop();
      for(int to : g[v]){
        if(depth[to] == -1) depth[to] = depth[v] + 1, q.push(to);
      }
    }
    //cout << cnt;
    for(int i = n; i < 2 * n; i++){
       // cout << depth[i] << ' ';
        if(depth[i] == -1) continue;
        vv[ind][depth[i] % cnt].pb(depth[i]);
    }
    for(int i = 0; i < cnt; i++)
      sort(vv[ind][i].begin(), vv[ind][i].end());
}

void count_routes(int n, int m, int p, int r[][2], int q, int qv[]){
    int f[n];
   // cout << 1;
    fill(f, f + n, -1);
    fill(nx, nx + 2 * n, -1);
    for(int i = 0; i < m; i++){
        int u = r[i][0], v = r[i][1];
        //cout << u << ' ' << v;
        if(f[u] == -1 && f[v] == -1){
            nx[u + n] = v;
            nx[v + n] = u;
        }
        if(f[u] == -1 && f[v] == 1){
            nx[u + n] = v + n;
            if(nx[v] == -1) nx[v] = u;
        }
        if(f[v] == -1 && f[u] == 1){
            nx[v + n] = u + n;
            if(nx[u] == -1) nx[u] = v; 
        }
        if(f[v] == 1 && f[u] == 1){
            if(nx[u] == -1) nx[u] = v + n;
            if(nx[v] == -1) nx[v] = u + n;
        }
        f[u] = f[v] = 1;
    }
   // cout << 1;
    for(int i = 0; i < 2 * n; i++){
      if(nx[i] == -1 && i < n){
          nx[i] = nx[i + n];
      }
     // cout << nx[i] << ' ';
      if(nx[i] != -1)   g[nx[i]].pb(i);
    }

  bfs(p, 0, n);
    bfs(p + n, 1, n);
    for(int i = 0; i < q; i++){
      int k = qv[i];
      int l = vv[0].size();
      int o = k % l;
      int ans = 0;
      ans += upper_bound(vv[0][o].begin(), vv[0][o].end(), k) - vv[0][o].begin();
      if(l == 1) ans -= lower_bound(vv[0][o].begin(), vv[0][o].end(), k) - vv[0][o].begin();
      l = vv[1].size();
      o = k % l;
      ans += upper_bound(vv[1][o].begin(), vv[1][o].end(), k) - vv[1][o].begin();
     if(l == 1) ans -= lower_bound(vv[1][o].begin(), vv[1][o].end(), k) - vv[1][o].begin();
      answer(ans);
    }
}

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