oj.uz

Submission #685222

# Submission time Handle Problem Language Result Execution time Memory
685222 2023-01-23T17:18:52 Z cadmiumsky Tropical Garden (IOI11_garden) C++14
100 / 100
 4166 ms 47412 KB 
#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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 7 ms 14396 KB Output is correct
5 Correct 7 ms 14496 KB Output is correct
6 Correct 9 ms 14684 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14560 KB Output is correct
9 Correct 10 ms 14896 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 7 ms 14396 KB Output is correct
5 Correct 7 ms 14496 KB Output is correct
6 Correct 9 ms 14684 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14560 KB Output is correct
9 Correct 10 ms 14896 KB Output is correct
10 Correct 8 ms 14424 KB Output is correct
11 Correct 18 ms 17912 KB Output is correct
12 Correct 30 ms 20676 KB Output is correct
13 Correct 48 ms 35720 KB Output is correct
14 Correct 97 ms 34592 KB Output is correct
15 Correct 120 ms 35148 KB Output is correct
16 Correct 98 ms 30424 KB Output is correct
17 Correct 81 ms 28912 KB Output is correct
18 Correct 29 ms 20812 KB Output is correct
19 Correct 100 ms 34492 KB Output is correct
20 Correct 116 ms 35036 KB Output is correct
21 Correct 89 ms 30464 KB Output is correct
22 Correct 83 ms 28896 KB Output is correct
23 Correct 93 ms 36356 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 7 ms 14396 KB Output is correct
5 Correct 7 ms 14496 KB Output is correct
6 Correct 9 ms 14684 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14560 KB Output is correct
9 Correct 10 ms 14896 KB Output is correct
10 Correct 8 ms 14424 KB Output is correct
11 Correct 18 ms 17912 KB Output is correct
12 Correct 30 ms 20676 KB Output is correct
13 Correct 48 ms 35720 KB Output is correct
14 Correct 97 ms 34592 KB Output is correct
15 Correct 120 ms 35148 KB Output is correct
16 Correct 98 ms 30424 KB Output is correct
17 Correct 81 ms 28912 KB Output is correct
18 Correct 29 ms 20812 KB Output is correct
19 Correct 100 ms 34492 KB Output is correct
20 Correct 116 ms 35036 KB Output is correct
21 Correct 89 ms 30464 KB Output is correct
22 Correct 83 ms 28896 KB Output is correct
23 Correct 93 ms 36356 KB Output is correct
24 Correct 8 ms 14420 KB Output is correct
25 Correct 150 ms 18040 KB Output is correct
26 Correct 206 ms 20892 KB Output is correct
27 Correct 3689 ms 35812 KB Output is correct
28 Correct 1246 ms 34892 KB Output is correct
29 Correct 4166 ms 35280 KB Output is correct
30 Correct 2435 ms 30504 KB Output is correct
31 Correct 2261 ms 28992 KB Output is correct
32 Correct 175 ms 20812 KB Output is correct
33 Correct 1259 ms 34632 KB Output is correct
34 Correct 4111 ms 35148 KB Output is correct
35 Correct 2538 ms 30540 KB Output is correct
36 Correct 2797 ms 28992 KB Output is correct
37 Correct 1058 ms 36428 KB Output is correct
38 Correct 3299 ms 47412 KB Output is correct