제출 #103459

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

garden

#include <bits/stdc++.h>
#include "gardenlib.h"
#include "garden.h"
#define lsb(x) (x & (-x))

using namespace std;

typedef vector <int> VI;
typedef vector <VI> VVI;
typedef pair <int, int> PII;
typedef vector <PII> VPII;
typedef vector <VPII> VVPII;

void count_routes(int n, int m, int p, int R[][2], int q, int G[]) {
    VVI g(n + 1);
    int i;
    for(i = 0; i < m; i++) {
        R[i][0]++, R[i][1]++;
        g[R[i][0]].push_back(i);
        g[R[i][1]].push_back(i);
    }
    for(i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
    }
    VVI anc(2 * n + 1, VI(30));
    for(i = 1; i <= n; i++) {
        int nod = (R[g[i][0]][0] ^ R[g[i][0]][1] ^ i);
        if(g[nod][0] == g[i][0]) {
            anc[i][0] = nod + n;
        }
        else {
            anc[i][0] = nod;
        }
        if(g[i].size() == 1) {
            if(g[nod][0] == g[i][0]) {
                anc[i + n][0] = nod + n;
            }
            else {
                anc[i + n][0] = nod;
            }
        }
        else {
            nod = (R[g[i][1]][0] ^ R[g[i][1]][1] ^ i);
            if(g[nod][0] == g[i][1]) {
                anc[i + n][0] = nod + n;
            }
            else {
                anc[i + n][0] = nod;
            }
        }
    }
    unordered_map <int, int> mp;
    for(int bit = 0; bit < 30; bit++) {
        mp[1 << bit] = bit;
    }
    for(int bit = 1; bit < 30; bit++) {
        for(i = 1; i <= 2 * n; i++) {
            anc[i][bit] = anc[anc[i][bit - 1]][bit - 1];
        }
    }
    p++;
    for(int t = 0; t < q; t++) {
        int ans = 0;
        for(i = 1; i <= n; i++) {
            int nod = i, aux = G[t];
            while(aux > 0) {
                int cur = lsb(aux);
                nod = anc[nod][mp[cur]];
                aux -= cur;
            }
            if(nod == p || nod == n + p) {
                ans++;
            }
        }
        answer(ans);
    }
}

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