Submission #447112

#	Time	Username	Problem	Language	Result	Execution time	Memory
447112		cs71107	Tropical Garden (IOI11_garden)	C++14	0 / 100	2 ms	460 KiB

garden

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

#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

int id[MAXN];
int iid[MAXN];
pii edge[MAXN];
bool chk[MAXN];

int dist[MAXN];

int D[MAXN];
int DD[MAXN];

inline void addedge(int x,int y,int idx){

    if(chk[x]){
        graph[(x<<1)].push_back(y);
    }
    else if(id[x]^idx){
        graph[(x<<1)].push_back(y);
    }
    else {
        graph[(x<<1)|1].push_back(y);
    }

    return;
}

int cyver = -1;

void dfs(int here){

    int there;

    for(int i=0;i<graph[here].size();i++){
        there = graph[here][i];
        if(dist[there]!=INF){
            cyver = here;
            continue;
        }
        dist[there] = dist[here]+1;
        dfs(there);
    }

    return;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  int n = N;
  int m = M;
  int k = P;

  int a,b;
  int cur,idx = -1;
  int cnt = 0;

  for(int i=0;i<m;i++){
    edge[i].f = R[i][0];
    edge[i].s = R[i][1];
  }

  fill(id,id+n,-1);
  fill(iid,iid+n,-1);

  for(int i=m-1;i>=0;i--){

      a = edge[i].f;
      b = edge[i].s;

      iid[a] = id[a];
      id[a] = i;
      iid[b] = id[b];
      id[b] = i;
  }

  for(int i=0;i<n;i++){
      chk[i] = (iid[i]==-1);
  }

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

      idx = id[i];

      a = edge[idx].f;
      b = edge[idx].s;

      if(a^i){
          addedge(a,(i<<1),idx);
      }
      else {
          addedge(b,(i<<1),idx);
      }

      if(chk[i])continue;

      idx = iid[i];

      a = edge[idx].f;
      b = edge[idx].s;

      if(a^i){
          addedge(a,(i<<1)|1,idx);
      }
      else {
          addedge(b,(i<<1)|1,idx);
      }
  }

  /*
  for(int i=0;i<(n<<1);i++){
      cout<<i<<" ";
      for(int j=0;j<(int)graph[i].size();j++){
          cout<<graph[i][j]<<" ";
      }
      cout<<"\n";
  }*/

  int cy = -1;
  int cyy = -1;

  fill(dist,dist+(n<<1),INF);
  dist[(k<<1)] = 0;
  cyver = -1;

  dfs((k<<1));

  if(cyver==-1)cy = 0;
  else cy = dist[cyver]+1;

  for(int i=0;i<(n<<1);i++){
      D[i] = dist[i];
  }

  //cout<<cy<<"\n";

  /*
  for(int i=0;i<(n<<1);i++){
      cout<<D[i]<<" ";
  }
  cout<<"\n";*/

  fill(dist,dist+(n<<1),INF);
  dist[(k<<1)|1] = 0;
  cyver = -1;

  dfs((k<<1)|1);

  if(cyver==-1)cyy = 0;
  else cyy = dist[cyver]+1;

  for(int i=0;i<(n<<1);i++){
      DD[i] = dist[i];
  }

  /*
  cout<<cyy<<"\n";

  for(int i=0;i<(n<<1);i++){
      cout<<DD[i]<<" ";
  }
  cout<<"\n";*/

  int vv = 0;

  for(int i=0;i<Q;i++){
      
      vv = G[i];

      cnt = 0;

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

          if(!cy){
              if(D[(i<<1)]==k)cnt++;
          }
          else {
              if(D[(i<<1)]<=k){
                  cur = (k-D[(i<<1)]);
                  if(!(cur%cy))cnt++;
              }
          }

          if(!cyy){
              if(DD[(i<<1)]==k)cnt++;
          }
          else {
              if(DD[(i<<1)]<=k){
                  cur = (k-DD[(i<<1)]);
                  if(!(cur%cyy))cnt++;
              }
          }
      }

      answer(cnt);
  }

  return;
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int)':
garden.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<graph[here].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:188:7: warning: variable 'vv' set but not used [-Wunused-but-set-variable]
  188 |   int vv = 0;
      |       ^~

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