제출 #564382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
564382		hoanghq2004	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	69 / 100	5061 ms	53580 KiB

garden

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "garden.h"
#include "gardenlib.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

vector <pair <int, int>> e[N];
int to[N][30];

//void answer(int x) {
//    cout << x << '\n';
//}

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
    vector <pair <int, int>> edges;
    for (int i = 0; i < m; ++i) {
        e[r[i][0]].push_back({r[i][1], i << 1});
        e[r[i][1]].push_back({r[i][0], i << 1 ^ 1});
        edges.push_back({r[i][0], r[i][1]});
        edges.push_back({r[i][1], r[i][0]});
    }
    for (int i = 0; i < m * 2; ++i) {
        auto [u, v] = edges[i];
        to[i][0] = -1;
        for (auto [w, j]: e[v]) {
            if (i / 2 == j / 2) continue;
            to[i][0] = j;
            break;
        }
        if (to[i][0] == -1) to[i][0] = e[v][0].second;
    }
    for (int lg = 1; lg <= 29; ++lg) {
        for (int i = 0; i < m * 2; ++i)
            to[i][lg] = to[to[i][lg - 1]][lg - 1];
    }
    for (int id = 0; id < q; ++id) {
        int x = g[id];
        int ans = 0;
        for (int r = 0; r < n; ++r) {
            int i = e[r][0].second;
            for (int lg = 29, y = x; lg >= 0; --lg) {
                if (y >= (1 << lg)) {
                    y -= (1 << lg);
                    i = to[i][lg];
                }
            }
            if (edges[i].first == p) ++ans;
        }
        answer(ans);
    }
}
//
//int main() {
//    int n, m, p;
//    cin >> n >> m >> p;
//    int r[m][2];
//    for (int i = 0; i < m; ++i) {
//        int u, v;
//        cin >> u >> v;
//        r[i][0] = u, r[i][1] = v;
//    }
//    int q;
//    cin >> q;
//    int g[q];
//    for (int i = 0; i < q; ++i) cin >> g[i];
//    count_routes(n, m, p, r, q, g);
//}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         auto [u, v] = edges[i];
      |              ^
garden.cpp:35:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         for (auto [w, j]: e[v]) {
      |                   ^

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31