oj.uz

답안 #1008301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008301 2024-06-26T09:03:43 Z c2zi6 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
100 / 100
 1868 ms 33876 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "garden.h"
#include "gardenlib.h"

void BFS(VVI& gp, int s, VI& dist) {
    int n = gp.size();
    queue<int> q;
    dist = VI(n, -1);
    dist[s] = 0;
    q.push(s);
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int v : gp[u]) if (v != s) {
            dist[v] = dist[u]+1;
            q.push(v);
        }
    }
}

int floyd(int s, VI& gp, VI& cycle) {
    if (gp[s] == -1) return 0;
    int cnt = 0;
    int u = s;
    int v = s;
    do {
        u = gp[u];
        v = gp[gp[v]];
    } while (u != v);
    do {
        u = gp[u];
        cycle[u] = true;
        cnt++;
    } while (u != v);
    return cnt;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    int n = N;
    int m = M;
    VVI initgp(n);
    rep(i, m) {
        int u = R[i][0];
        int v = R[i][1];
        initgp[u].pb(v);
        initgp[v].pb(u);
    }
    VI gp(2*n, -1);
    rep(u, n) {int v;
        v = initgp[u][0];
        if (initgp[v].size() == 1 || initgp[v][0] != u) {
            gp[u] = v;
        } else {
            gp[u] = v+n;
        }
        if (initgp[u].size() == 1) continue;
        v = initgp[u][1];
        if (initgp[v].size() == 1 || initgp[v][0] != u) {
            gp[u+n] = v;
        } else {
            gp[u+n] = v+n;
        }
    }

    /*cout << "Expected: ";*/
    /*auto erexa = [&](int u, int k) {*/
    /*    while (k--) u = gp[u];*/
    /*    return u;*/
    /*};*/
    /*rep(i, Q) {*/
    /*    int ans = 0;*/
    /*    rep(u, n) {*/
    /*        int x = erexa(u, G[i]);*/
    /*        if (x == P || x == P+n) ans++;*/
    /*    }*/
    /*    cout << ans << " ";*/
    /*}*/
    /*cout << endl;*/

    auto val = [&](int u) {
        if (u < n) return to_string(u);
        return to_string(u-n) + "*";
    };

    VI cycle(2*n);
    int lng1 = floyd(P, gp, cycle);
    int lng2 = floyd(P+n, gp, cycle);
    VVI trans(2*n);
    rep(u, 2*n) if (gp[u] != -1) trans[gp[u]].pb(u);
    VI dist1, dist2;
    BFS(trans, P, dist1);
    BFS(trans, P+n, dist2);
    rep(i, Q) { int k = G[i];
        int ans = 0;
        if (cycle[P]) {
            rep(u, n) if (dist1[u] != -1) {
                ans += (dist1[u]%lng1 == k%lng1 && k >= dist1[u]);
            }
        } else {
            rep(u, n) {
                ans += (dist1[u] == k);
            }
        }

        if (gp[P+n] != -1) {
            if (cycle[P+n]) {
                rep(u, n) if (dist2[u] != -1) {
                    ans += (dist2[u]%lng2 == k%lng2 && k >= dist2[u]);
                }
            } else {
                rep(u, n) {
                    ans += (dist2[u] == k);
                }
            }
        }
        answer(ans);
    }
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:110:10: warning: variable 'val' set but not used [-Wunused-but-set-variable]
  110 |     auto val = [&](int u) {
      |          ^~~

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 8 ms 6668 KB Output is correct
12 Correct 23 ms 9524 KB Output is correct
13 Correct 29 ms 20052 KB Output is correct
14 Correct 59 ms 26724 KB Output is correct
15 Correct 54 ms 27224 KB Output is correct
16 Correct 44 ms 19988 KB Output is correct
17 Correct 50 ms 17488 KB Output is correct
18 Correct 16 ms 9564 KB Output is correct
19 Correct 48 ms 26864 KB Output is correct
20 Correct 56 ms 27220 KB Output is correct
21 Correct 45 ms 19864 KB Output is correct
22 Correct 48 ms 17744 KB Output is correct
23 Correct 48 ms 29264 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 8 ms 6668 KB Output is correct
12 Correct 23 ms 9524 KB Output is correct
13 Correct 29 ms 20052 KB Output is correct
14 Correct 59 ms 26724 KB Output is correct
15 Correct 54 ms 27224 KB Output is correct
16 Correct 44 ms 19988 KB Output is correct
17 Correct 50 ms 17488 KB Output is correct
18 Correct 16 ms 9564 KB Output is correct
19 Correct 48 ms 26864 KB Output is correct
20 Correct 56 ms 27220 KB Output is correct
21 Correct 45 ms 19864 KB Output is correct
22 Correct 48 ms 17744 KB Output is correct
23 Correct 48 ms 29264 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 75 ms 6744 KB Output is correct
26 Correct 123 ms 9552 KB Output is correct
27 Correct 1221 ms 20304 KB Output is correct
28 Correct 650 ms 26904 KB Output is correct
29 Correct 1249 ms 27344 KB Output is correct
30 Correct 801 ms 19772 KB Output is correct
31 Correct 663 ms 17492 KB Output is correct
32 Correct 105 ms 9564 KB Output is correct
33 Correct 665 ms 26900 KB Output is correct
34 Correct 1244 ms 27328 KB Output is correct
35 Correct 829 ms 20000 KB Output is correct
36 Correct 715 ms 17716 KB Output is correct
37 Correct 678 ms 29200 KB Output is correct
38 Correct 1868 ms 33876 KB Output is correct