제출 #1032195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032195		VMaksimoski008	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	69 / 100	5078 ms	68180 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

const int maxn = 3e5 + 5;

vector<int> graph_shit[maxn+5];
vector<int> graph[maxn+5];
int n, up[maxn][31];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    n = N;

    for(int i=0; i<M; i++) {
        graph_shit[R[i][0]].push_back(R[i][1]);
        graph_shit[R[i][1]].push_back(R[i][0]);
    }

    for(int i=0; i<N; i++) {
        int v = graph_shit[i][0];
        if(graph_shit[v][0] == i) graph[i].push_back(v+N);
        else graph[i].push_back(v);
    }

    for(int i=N; i<2*N; i++) {
        if(graph_shit[i-N].size() == 1) {
            int v = graph_shit[i-N][0];
            if(graph_shit[v][0] == i-N) graph[i].push_back(v+N);
            else graph[i].push_back(v);
        } else {
            int v = graph_shit[i-N][1];
            if(graph_shit[v][0] == i-N) graph[i].push_back(v+N);
            else graph[i].push_back(v);
        }
    }

    for(int i=0; i<2*N; i++) up[i][0] = graph[i].back();

    for(int j=1; j<31; j++)
        for(int i=0; i<2*N; i++) up[i][j] = up[up[i][j-1]][j-1];

    for(int i=0; i<Q; i++) {
        int ans=0;

        for(int j=0; j<N; j++) {
            int curr = j;
            for(int k=30; k>=0; k--)
                if(G[i] & (1ll << k)) curr = up[curr][k];
            if(curr == P || curr == P + N) ans++;
        }

        answer(ans);
    }
}

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