제출 #374222

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

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int MAXN = (int)(150000);
const int INF = (int)(2e9);
vector<int> revadj[2*MAXN];
int first[MAXN];
int second[MAXN];
int to[2*MAXN];
bool seen[2*MAXN];
int dist[2*MAXN][2];
int oppose(int a, int r[2]) {
    if (r[0] == a) {
        return r[1];
    }
    return r[0];
}
int checkLoop(int start) {
    memset(seen, 0, sizeof(seen));
    int ori = start;
    int cnt = 1;
    seen[start] = true;
    while (!seen[to[start]]) {
        cnt++;
        start = to[start];
        seen[start] = true;
    }
    start = to[start];
    if (ori != start) {
        return INF;
    }
    else {
        return cnt;
    }
}
void mdist(int start) {
    int id = start&1;
    for (int i = 0; i < 2*MAXN; i++){
        dist[i][id] = INF;
    }
    deque<int> deq;
    deq.push_back(start);
    dist[start][id] = 0;
    while (deq.size()) {
        int n = deq.front();
        deq.pop_front();
        for (int e : revadj[n]) {
            if (dist[e][id] > dist[n][id] + 1) {
                dist[e][id] = dist[n][id]+1;
                deq.push_back(e);
            }
        }
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    fill(all(first), -1);
    fill(all(second), -1);
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < 2; j++) {
            if (first[R[i][j]] == -1) {
                first[R[i][j]] = i;
            }
            else if (second[R[i][j]] == -1) {
                second[R[i][j]] = i;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        int fv = oppose(i, R[first[i]]);
        if (first[fv] == first[i]) {
            to[2*i] = 2*fv+1;
        }
        else {
            to[2*i] = 2*fv;
        }
        if (second[i] != -1) {
            int sv = oppose(i, R[second[i]]);
            if (first[sv] == second[i]) {
                to[2*i+1] = 2*sv+1;
            }
            else {
                to[2*i+1] = 2*sv;
            }
        }
        else {
            to[2*i+1] = to[2*i];
        }
        revadj[to[2*i]].push_back(2*i);
        revadj[to[2*i+1]].push_back(2*i+1);
    }
    int lp[2];
    lp[0] = checkLoop(2*P);
    lp[1] = checkLoop(2*P+1);
    mdist(2*P);
    mdist(2*P+1);
    for (int iter = 0; iter < Q; iter++) {
        int k = G[iter];
        int cnt = 0;
        for (int i =0; i < 2*N; i+=2) {
            bool good = false;
            if (dist[i][0] <= k && (k-dist[i][0])%lp[0] == 0) {
                good = true;
            }
            if (dist[i][1] <= k && (k-dist[i][1])%lp[1] == 0) {
                good = true;
            }
            cnt += good;
        }
        answer(cnt);
    }
}

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