Submission #685222

#	Time	Username	Problem	Language	Result	Execution time	Memory
685222		cadmiumsky	Tropical Garden (IOI11_garden)	C++14	100 / 100	4166 ms	47412 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

using ll = long long;
//#define int ll 

#define sz(x) (x).size()


using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 3e5 + 5, inf = 1e9 + 5;

namespace G {
  int n;
  int target[nmax];
  vector<int> trans[nmax];
  int isspecial[nmax];
  vector<int> lst;
  int addnode(int x = 0) { 
    isspecial[n] = x;
    if(x)
      lst.emplace_back(n);
    return n++;
  }
  void addedge(int x, int y) { // SIIGUR ESTE FUNCTIONAL
    target[x] = y;
    trans[y].emplace_back(x);
    //cerr << x << " -> " << y << '\n';
  }
  
  int flag = 0;
  int K[2];
  
  int occ[nmax];
  int isoncycle[nmax];
  int findcycdim(int node) {
    ++flag;
    if(occ[node] != 0)
      return flag - occ[node];
    occ[node] = flag;
    int rez = findcycdim(target[node]);
    if(flag - occ[node] <= rez) isoncycle[node] = 1;
    return rez;
  }
  void findcycdim(int P1, int P2) {
    K[0] = findcycdim(P1);
    for(int i = 0; i < n; i++)
      occ[i] = 0;
    flag = 0;
    K[1] = findcycdim(P2);
  }
  
  int prec[nmax * 2];
  
  void dfs(int node, int *time, int atr = 0) {
    queue<int> que;
    que.emplace(node);
    time[node] = 0;
    while(!que.empty()) {
      int node = que.front();
      //cerr << node << ' ' << occ[node] << ' ' << time[node] << '\n';
      que.pop();
      if(occ[node] == 1) continue;
      occ[node] = 1;
      for(auto x : trans[node]) {
        if(occ[x] == 0 && time[node] + 1 < time[x]) {
          time[x] = time[node] + 1;
          que.emplace(x);
        }
      }
    }
    
    return;
  }
  int time[2][nmax];
  int how[2];
  
  void countprec(int P1, int P2) {
    for(int i = 0; i < n; i++)
      occ[i] = 0, time[0][i] = inf;
    for(int i = 0; i < n; i++) time[1][i] = inf;
    
    if(isoncycle[P1])
      how[0] = 1;
    if(isoncycle[P2])
      how[1] = 1;
      
    dfs(P1, time[0], 0);
    if(P2 != P1) {
      for(int j = 0; j < n; j++)
        occ[j] = 0;
      dfs(P2, time[1], 0);
    }
    else 
      how[1] = 0;
    flag = 3;
    
    
    return;
  }
  
  int count(int A) {
    flag++;
    int cnt = 0;
    for(auto i : lst) {
      if(time[0][i] == A || (how[0] == 1 && time[0][i] <= A && time[0][i] % K[0] == A % K[0]))
        occ[i] = flag, cnt++;
    }
    for(auto i : lst) {
      if(occ[i] == flag) continue;
      if(time[1][i] == A || (how[1] == 1 && time[1][i] <= A && time[1][i] % K[1] == A % K[1]))
        occ[i] = flag, cnt++;
    }
    //for(int i = 0; i < n; i++)
      //cerr << occ[i] << ' ';
    //cerr << '\n';
    return cnt;
  }
  
}

vector<pii> g[nmax];

int atr[nmax][2];
pii atre[nmax][2];

void count_routes(int n, int m, int P, int R[][2], int Q, int G[]) {
  G::lst.reserve(nmax);
  for(int i = 0; i < m; i++) {
    g[R[i][0]].emplace_back(R[i][1], m - i);
    g[R[i][1]].emplace_back(R[i][0], m - i);
  }
  
  
  
  for(int i = 0; i < n; i++) {
    atr[i][0] = atr[i][1] = -1;
    if(sz(g[i]) == 0) continue;
    atr[i][0] = atr[i][1] = G::addnode(1);
    if(sz(g[i]) == 1) continue;
    atr[i][1] = G::addnode();
  }
  
  for(int i = 0; i < n; i++) {
    //cerr << atr[i][0] << ' ' << atr[i][1] << '\n';
    atre[i][0] = atre[i][1] = pii{-1, -1};
    for(auto [x, e] : g[i]) {
      if(atre[i][0].second < e) {
        atre[i][1] = atre[i][0];
        atre[i][0] = pii{x, e};
      }
      else if(atre[i][1].second < e) 
        atre[i][1] = pii{x, e};
    }
  }
  
  for(int i = 0; i < n; i++) {
    if(sz(g[i]) == 0) continue; 
    auto [x, e] = atre[i][0];
    if(atre[x][0].second == e)
      G::addedge(atr[i][0], atr[x][1]);
    else
      G::addedge(atr[i][0], atr[x][0]);
    if(sz(g[i]) == 1) continue;
    tie(x, e) = atre[i][1];
    if(atre[x][0].second == e)
      G::addedge(atr[i][1], atr[x][1]);
    else
      G::addedge(atr[i][1], atr[x][0]);
  }
  
  G::findcycdim(atr[P][0], atr[P][1]);
  G::countprec(atr[P][0], atr[P][1]);
  
  for(int i = 0; i < Q; i++) {
    answer(G::count(G[i]));
  }
  return;
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:151:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |     for(auto [x, e] : g[i]) {
      |              ^
garden.cpp:163:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |     auto [x, e] = atre[i][0];
      |          ^

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