제출 #433124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433124		someone	Tropical Garden (IOI11_garden)	C++14	49 / 100	522 ms	67556 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int i, t;
};

struct Req {
    bool add;
    int t, k, id;
};

const int N = 3e5 + 42, Q = 2e3 + 10, INF = 2e9;

bool b[N][2];
Node nex[N][2];
vector<int> adj[N];
vector<Node> pre[N][2];
int n, m, fin, q, step[Q], occ[N][2], arc[N], cycle[2], dist[N][2][2], ans[N];

void BFS(int k) {
    queue<Node> q;
    q.push({fin, k});
    dist[fin][k][k] = 0;
    while(!q.empty()) {
        Node act = q.front();
        q.pop();
        for(Node next : pre[act.i][act.t]) {
            if(dist[next.i][next.t][k] == INF) {
                dist[next.i][next.t][k] = dist[act.i][act.t][k] + 1;
                q.push(next);
            }
        }
    }
}

void count_routes(int N_, int M_, int P_, int R[][2], int Q_, int G[]) {
    n = N_, m = M_, fin = P_, q = Q_;
    for(int i = 0; i < m; i++)
        arc[i] = R[i][0] + R[i][1];
    for(int i = 0; i < m; i++) {
        if(adj[R[i][0]].size() < 2) {
            adj[R[i][0]].push_back(i);
        }
        if(adj[R[i][1]].size() < 2) {
            adj[R[i][1]].push_back(i);
        }
    }
    for(int i = 0; i < n; i++)
        if(adj[i].size() == 1)
            adj[i].push_back(adj[i][0]);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < 2; j++) {
            int s = arc[adj[i][j]] - i;
            if(adj[i][j] == adj[s][0]) {
                nex[i][j] = {s, 1};
                pre[s][1].push_back({i, j});
            } else {
                nex[i][j] = {s, 0};
                pre[s][0].push_back({i, j});
            }
        }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                dist[i][j][k] = INF;
    int i = fin, j = 0, nb = 0;
    cycle[0] = cycle[1] = -1;
    do {
        nb++;
        b[i][j] = true;
        Node next = nex[i][j];
        i = next.i;
        j = next.t;
    } while(!b[i][j]);
    if(i == fin && j == 0) {
        cycle[0] = nb;
    }
    for(int i = 0; i < n; i++)
        b[i][0] = b[i][1] = false;
    i = fin, j = 1, nb = 0;
    do {
        nb++;
        b[i][j] = true;
        Node next = nex[i][j];
        i = next.i;
        j = next.t;
    } while(!b[i][j]);
    if(i == fin && j == 1) {
        cycle[1] = nb;
    }
    BFS(0);
    BFS(1);
    vector<Req> req;
    for(int i = 0; i < n; i++)
        for(int k = 0; k < 2; k++)
            if(dist[i][0][k] != INF)
                req.push_back({true, dist[i][0][k], k, 0});
    for(int i = 0; i < q; i++)
        req.push_back({false, G[i], 0, i});
    sort(req.begin(), req.end(),
    [](Req a, Req b) {
        if(a.t == b.t)
            return a.add;
        return a.t < b.t;
    });

    for(Req r : req) {
        if(r.add) {
            if(cycle[r.k] == -1) {
                occ[r.t][r.k]++;
            } else {
                occ[r.t % cycle[r.k]][r.k]++;
            }
        } else {
            if(cycle[0] == -1) {
                if(r.id < N)
                    ans[r.id] += occ[r.t][0];
            } else {
                ans[r.id] += occ[r.t % cycle[0]][0];
            }
            if(cycle[1] == -1) {
                if(r.id < N)
                    ans[r.id] += occ[r.t][1];
            } else {
                ans[r.id] += occ[r.t % cycle[1]][1];
            }
        }
    }
    for(int i = 0; i < q; i++)
        answer(ans[i]);
}

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