Submission #1263899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263899		julia_08	Tropical Garden (IOI11_garden)	C++20	100 / 100	1718 ms	63844 KiB

garden

#include <bits/stdc++.h>

#include "garden.h"
#include "gardenlib.h"

using namespace std;

const int MAXN = 3e5 + 10;

vector<pair<int, int>> edges[MAXN];

vector<int> adj[MAXN][2];

int dist[MAXN][2];

int marc[MAXN], comp[MAXN];

int sz[MAXN], deg[MAXN];

void dfs_1(int v, int x){

  marc[v] = 1;

  for(auto u : adj[v][1]){
    if(!marc[u]){
      dist[u][x] = dist[v][x] + 1;
      dfs_1(u, x);
    }
  }

}

void dfs_2(int v, int c){

  comp[v] = c;
  sz[c] ++;

  for(auto u : adj[v][0]){
    if(deg[u] == 0) continue;
    if(!comp[u]) dfs_2(u, c);
  }

}

void lenhadora(int n){

  queue<int> q;

  for(int i=0; i<(2 * n); i++){
    if(deg[i] == 0){
      q.push(i);
    }
  }

  while(!q.empty()){

    int v = q.front();
    q.pop();

    for(auto u : adj[v][0]){
      deg[u] --;
      if(deg[u] == 0) q.push(u);
    }

  }

}

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

  for(int i=0; i<(2 * n); i++){
    
    marc[i] = comp[i] = 0;
    dist[i][0] = dist[i][1] = -1;
    
    adj[i][0].clear();
    adj[i][1].clear();
  
  }

  for(int i=0; i<m; i++){
    edges[r[i][0]].push_back({i, r[i][1]});
    edges[r[i][1]].push_back({i, r[i][0]});
  }

  for(int i=0; i<n; i++) sort(edges[i].begin(), edges[i].end());

  for(int i=0; i<n; i++){

    for(int k=0; k<2; k++){

      int x = 0;

      if(k == 1 && edges[i].size() == 1) x = 1;

      auto [e, j] = edges[i][(x ? 0 : k)];

      if(e != edges[j][0].first){

        adj[i + k * n][0].push_back(j);
        adj[j][1].push_back(i + k * n);

        deg[j] ++;

      } else{

        adj[i + k * n][0].push_back(j + n);
        adj[j + n][1].push_back(i + k * n);

        deg[j + n] ++;

      }

    }

  }

  dist[p][0] = 0;
  dfs_1(p, 0);

  for(int i=0; i<(2 * n); i++) marc[i] = 0;

  dist[p + n][1] = 0;
  dfs_1(p + n, 1);

  lenhadora(n);

  int c = 0;

  for(int i=0; i<(2 * n); i++){
    if(deg[i] == 0) continue;
    if(!comp[i]) dfs_2(i, ++c);
  }

  for(int i=0; i<q; i++){

    int cnt = 0;

    for(int j=0; j<n; j++){

      bool ok = false;

      for(int k=0; k<2; k++){

        if(dist[j][k] == -1) continue;

        int sz_c = sz[comp[p + k * n]];

        if(sz_c == 0){
          ok |= (dist[j][k] == g[i]);

        } else if(dist[j][k] <= g[i]) ok |= ((g[i] - dist[j][k]) % sz_c == 0);

      }

      cnt += ok;

    }

    answer(cnt);

  }

}

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