oj.uz

Submission #751135

# Submission time Handle Problem Language Result Execution time Memory
751135 2023-05-31T05:43:35 Z marvinthang Tropical Garden (IOI11_garden) C++17
69 / 100
 95 ms 32720 KB 
/*************************************
*    author: marvinthang             *
*    created: 31.05.2023 11:52:41    *
*************************************/

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    vector <int> nxt(N + N);
    vector <vector <int>> adj(N + N);
    vector <pair <int, int>> max_edge(N, make_pair(-1, -1));
    REP(i, M) {
        int u = R[i][0], v = R[i][1];
        if (max_edge[u].fi == -1) max_edge[u].fi = v;
        else if (max_edge[u].se == -1) max_edge[u].se = v;
        if (max_edge[v].fi == -1) max_edge[v].fi = u;
        else if (max_edge[v].se == -1) max_edge[v].se = u;
    }
    REP(u, N) {
        int v = max_edge[u].fi;
        nxt[u] = max_edge[v].fi == u ? v + N : v;
        v = max_edge[u].se;
        nxt[u + N] = v == -1 ? nxt[u] : max_edge[v].fi == u ? v + N : v;
    }
    REP(u, N + N) adj[nxt[u]].push_back(u);
    vector <int> res(N);
    auto solve = [&] (int t) {
        vector <bool> visited(N + N);
        int cnt = 0;
        int u = t;
        while (!visited[u]) {
            ++cnt;
            visited[u] = true;
            u = nxt[u];
        }
        if (u != t) {
            queue <int> q;
            q.push(t);
            vector <int> cnt(N + N);
            vector <int> dist(N + N, -1);
            dist[t] = 0;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                if (u < N) ++cnt[dist[u]];
                for (int v: adj[u]) if (dist[v] == -1) {
                    q.push(v);
                    dist[v] = dist[u] + 1;
                }
            }
            REP(i, Q) if (G[i] < N + N) res[i] += cnt[G[i]];
            return;
        }
        vector <int> cycle;
        vector <vector <int>> ver(N + N);
        do {
            u = nxt[u]; 
            cycle.push_back(u); 
        } while (u != t);        
        reverse(ALL(cycle));
        REP(i, cnt) ver[i].push_back(cycle[i]);
        vector <vector <int>> f(cnt, vector<int>((N + N) / cnt + 1));
        REP(d, N + N) for (int u: ver[d]) {
            if (u < N) f[d % cnt][d / cnt]++;
            for (int v: adj[u]) if (!visited[v]) {
                visited[v] = true;
                ver[d + 1].push_back(v);
            }
        }
        for (auto &v: f) partial_sum(ALL(v), v.begin());
        REP(i, Q) res[i] += f[G[i] % cnt][min((N + N) / cnt, G[i] / cnt)];
    };
    solve(P);
    solve(P + N);
    REP(i, Q) answer(res[i]);
}

#ifdef LOCAL
#include "garden.h"
#include "gardenlib.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX_M  1000000
#define MAX_Q  2000

static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;

inline 
void my_assert(int e) {if (!e) abort();}
void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&P));
  for(i=0; i<M; i++)
    my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
  my_assert(1==scanf("%d",&Q));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&G[i]));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&solutions[i]));
}

void answer(int x)
{
  if(answer_count>=Q) {
    printf("Incorrect.  Too many answers.\n");
    exit(0);
  }
  answers[answer_count] = x;
  answer_count++;
}

int main()
{
    file("garden");
  int correct, i;

  read_input();
  answer_count = 0;
  count_routes(N,M,P,R,Q,G);

  if(answer_count!=Q) {
    printf("Incorrect.  Too few answers.\n");
    exit(0);
  }

  correct = 1;
  for(i=0; i<Q; i++)
    if(answers[i]!=solutions[i])
      correct = 0;
  if(correct)
    printf("Correct.\n");
  else {
    printf("Incorrect.\n");
    printf("Expected: ");
    for(i=0; i<Q; i++)
      printf("%d ",solutions[i]);
    printf("\nReturned: ");
    for(i=0; i<Q; i++)
      printf("%d ",answers[i]);
  }
  return 0;
}

#endif

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 2 ms 544 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 2 ms 544 KB Output is correct
10 Correct 0 ms 316 KB Output is correct
11 Correct 10 ms 4532 KB Output is correct
12 Correct 20 ms 7256 KB Output is correct
13 Correct 70 ms 32720 KB Output is correct
14 Correct 72 ms 24252 KB Output is correct
15 Correct 94 ms 25692 KB Output is correct
16 Correct 66 ms 18620 KB Output is correct
17 Correct 60 ms 15772 KB Output is correct
18 Correct 17 ms 5760 KB Output is correct
19 Correct 70 ms 24200 KB Output is correct
20 Correct 95 ms 25524 KB Output is correct
21 Correct 67 ms 18392 KB Output is correct
22 Correct 62 ms 15480 KB Output is correct
23 Correct 79 ms 26660 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 2 ms 544 KB Output is correct
10 Correct 0 ms 316 KB Output is correct
11 Correct 10 ms 4532 KB Output is correct
12 Correct 20 ms 7256 KB Output is correct
13 Correct 70 ms 32720 KB Output is correct
14 Correct 72 ms 24252 KB Output is correct
15 Correct 94 ms 25692 KB Output is correct
16 Correct 66 ms 18620 KB Output is correct
17 Correct 60 ms 15772 KB Output is correct
18 Correct 17 ms 5760 KB Output is correct
19 Correct 70 ms 24200 KB Output is correct
20 Correct 95 ms 25524 KB Output is correct
21 Correct 67 ms 18392 KB Output is correct
22 Correct 62 ms 15480 KB Output is correct
23 Correct 79 ms 26660 KB Output is correct
24 Runtime error 1 ms 468 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -