oj.uz

Submission #787550

# Submission time Handle Problem Language Result Execution time Memory
787550 2023-07-19T09:33:10 Z Ronin13 Tropical Garden (IOI11_garden) C++17
49 / 100
 43 ms 27672 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 2 ms 5028 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5016 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 2 ms 5028 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5016 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 12 ms 7060 KB Output is correct
12 Correct 19 ms 8348 KB Output is correct
13 Correct 43 ms 27672 KB Output is correct
14 Runtime error 29 ms 16564 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 2 ms 5028 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5016 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 12 ms 7060 KB Output is correct
12 Correct 19 ms 8348 KB Output is correct
13 Correct 43 ms 27672 KB Output is correct
14 Runtime error 29 ms 16564 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -