oj.uz

Submission #776845

# Submission time Handle Problem Language Result Execution time Memory
776845 2023-07-08T10:18:54 Z I_Love_EliskaM_ Tropical Garden (IOI11_garden) C++14
69 / 100
 229 ms 82816 KB 
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()

bool foo(pi a, pi b) {
  return a.s < b.s;
}

const int _N=2e5;
const int K=30;
int up[2][_N][K];
int z[2][_N][K];
vector<pi> adj[_N];

int jump(int u, int x) {
  int from=-1;
  for (int j=0; (1<<j)<=x; ++j) {
    if ((x>>j)&1) {
      if (from==adj[u][0].f) {
        from=z[1][u][j];
        u=up[1][u][j];
      } else {
        from=z[0][u][j];
        u=up[0][u][j];
      } 
    } 
  }
  return u;
}

void count_routes(int n, int m, int p, int r[][2], int q, int *g) {
  
  forn(i,m) {
    int u=r[i][0], v=r[i][1];
    adj[u].pb({v,i});
    adj[v].pb({u,i});
  }
  forn(i,n) sort(all(adj[i]),foo);

  forn(i,n) {
    if (adj[i].size()>1) {
      up[0][i][0]=adj[i][0].f;
      up[1][i][0]=adj[i][1].f;
    } else {
      up[0][i][0]=up[1][i][0]=adj[i][0].f;
    }
    z[0][i][0]=z[1][i][0]=i;
  }
  for (int j=1; j<K; ++j) {
    forn(i,n) {
      forn(c,2) {
        int u=i, v=up[c][i][j-1];
        if (z[c][i][j-1]==adj[v][0].f) {
          up[c][i][j] = up[1][v][j-1];
          z[c][i][j] = z[1][v][j-1];
        } else {
          up[c][i][j] = up[0][v][j-1];
          z[c][i][j] = z[0][v][j-1];
        }
      }
    }
  }

  vector<pi> v; forn(i,q) v.pb({g[i],i});
  map<int,int> mem;
  vector<int> ans(q);
  int last=0;
  vector<int> f(n); forn(i,n) f[i]=i;
  forn(i,q) {
    int k=v[i].f;
    if (mem[k]) {
      ans[v[i].s]=mem[k]-1; continue;
    }
    int z=0;
    forn(j,n) {
      f[j]=jump(f[j],k-last);
      z+=f[j]==p;
    }
    mem[k]=z+1;
    ans[v[i].s]=z;
    last=k;
  }
  forn(i,q) answer(ans[i]);
  
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:58:13: warning: unused variable 'u' [-Wunused-variable]
   58 |         int u=i, v=up[c][i][j-1];
      |             ^

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5588 KB Output is correct
7 Correct 3 ms 4984 KB Output is correct
8 Correct 3 ms 5460 KB Output is correct
9 Correct 4 ms 5716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5588 KB Output is correct
7 Correct 3 ms 4984 KB Output is correct
8 Correct 3 ms 5460 KB Output is correct
9 Correct 4 ms 5716 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 20 ms 16620 KB Output is correct
12 Correct 52 ms 25032 KB Output is correct
13 Correct 167 ms 48620 KB Output is correct
14 Correct 200 ms 75284 KB Output is correct
15 Correct 202 ms 76192 KB Output is correct
16 Correct 179 ms 54124 KB Output is correct
17 Correct 120 ms 46856 KB Output is correct
18 Correct 47 ms 24908 KB Output is correct
19 Correct 205 ms 75228 KB Output is correct
20 Correct 190 ms 76264 KB Output is correct
21 Correct 144 ms 53964 KB Output is correct
22 Correct 139 ms 46592 KB Output is correct
23 Correct 229 ms 82816 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5588 KB Output is correct
7 Correct 3 ms 4984 KB Output is correct
8 Correct 3 ms 5460 KB Output is correct
9 Correct 4 ms 5716 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 20 ms 16620 KB Output is correct
12 Correct 52 ms 25032 KB Output is correct
13 Correct 167 ms 48620 KB Output is correct
14 Correct 200 ms 75284 KB Output is correct
15 Correct 202 ms 76192 KB Output is correct
16 Correct 179 ms 54124 KB Output is correct
17 Correct 120 ms 46856 KB Output is correct
18 Correct 47 ms 24908 KB Output is correct
19 Correct 205 ms 75228 KB Output is correct
20 Correct 190 ms 76264 KB Output is correct
21 Correct 144 ms 53964 KB Output is correct
22 Correct 139 ms 46592 KB Output is correct
23 Correct 229 ms 82816 KB Output is correct
24 Incorrect 5 ms 5204 KB Output isn't correct
25 Halted 0 ms 0 KB -