제출 #432971

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

garden

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

//  <|°_°|>

const int INFINI = (1000 * 1000 * 1000 + 1);
const int MAX_NOEUDS = (150 * 1000);
const int MAX_ARETES = (300 * 1000 + 1);
const int MAX_REQUETES = (2000);

vector <int> Voisins[MAX_NOEUDS];

bool Depart[MAX_ARETES];

bool Vu[MAX_ARETES];

int Fils[MAX_ARETES];

int Dist[MAX_ARETES];

pair <int, int> Ans[MAX_REQUETES];

int Occ[MAX_ARETES];

pair <int, int> AretesSorties;

void Set(int noeud, bool start) {
    int mini = INFINI, mini2 = INFINI;
    int dest = -1, dest2 = -1;
    for (int id : Voisins[noeud])
    {
        if (id / 2 < mini)
        {
            mini = id / 2;
            dest = id;
        }
    }
    dest2 = dest;
    for (int id : Voisins[noeud])
    {
        if (id / 2 != mini && id / 2 < mini2)
        {
            mini2 = id / 2;
            dest2 = id;
        }
    }
    for (int id : Voisins[noeud])
    {
        if (id != dest)
            Fils[id ^ 1] = dest;
        else
            Fils[id ^ 1] = dest2;
    }
    if (dest2 == dest)
        dest2 = -1;
    if (start)
        AretesSorties = {dest, dest2};
    Depart[dest] = true;
    return;
}

int FindDist(int noeud, int out) {
    if (noeud == out)
        return 0;
    if (Vu[noeud])
        return Dist[noeud];
    Vu[noeud] = true;
    return Dist[noeud] = FindDist(Fils[noeud], out) + 1;
}

void SetDist(int dep, int nbAretes) {
    for (int i = 0; i < nbAretes; i ++)
    {
        Dist[i] = INFINI;
        Vu[i] = false;
    }
    for (int i = 0; i < nbAretes; i ++)
    {
        if (!Vu[i])
            FindDist(i, dep);
    }
    return;
}

void count_routes(int nbNoeuds, int nbAretes, int sortie, int Aretes[][2], int nbRequetes, int Requetes[]) {
    
    for (int i = 0; i < nbAretes; i ++)
    {
        Voisins[Aretes[i][0]].push_back(2 * i);
        Voisins[Aretes[i][1]].push_back(2 * i + 1);
    }
    nbAretes *= 2;
    for (int i = 0; i < nbNoeuds; i ++)
    {
        Set(i, i == sortie);
    }
    for (int i = 0; i < nbRequetes; i ++)
    {
        Ans[i] = {Requetes[i], i};
    }
    sort(Ans, Ans + nbRequetes);
    for (int i = 0; i < nbRequetes; i ++)
    {
        Ans[i].first = 0;
    }
    SetDist(AretesSorties.first, nbAretes);
    int tailleCycle = Dist[Fils[AretesSorties.first]] + 1;
    Dist[AretesSorties.first] = tailleCycle;
    int maxi = 0;
    for (int i = 0; i < nbAretes; i ++)
    {
        if (Depart[i] && Dist[i] < INFINI)
        {
            maxi = max(maxi, Dist[i]);
            Occ[Dist[i]] ++;
        }
    }
    int cur = 0;
    for (int i = 0; i < nbRequetes; i ++)
    {
        while (cur <= min(maxi, Requetes[Ans[i].second]))
        {
            if (cur >= tailleCycle)
                Occ[cur % tailleCycle] += Occ[cur];
            cur ++;
        }
        if (Requetes[Ans[i].second] % tailleCycle < MAX_ARETES)
            Ans[i].first += Occ[Requetes[Ans[i].second] % tailleCycle];
    }
    if (AretesSorties.second >= 0)
    {
        SetDist(AretesSorties.second, nbAretes);
        tailleCycle = Dist[Fils[AretesSorties.second]] + 1;
        Dist[AretesSorties.second] = tailleCycle;
        
        for (int i = 0; i <= maxi; i ++)
        {
            Occ[i] = 0;
        }
        maxi = 0;
        for (int i = 0; i < nbAretes; i ++)
        {
            if (Depart[i] && Dist[i] < INFINI)
            {
                maxi = max(maxi, Dist[i]);
                Occ[Dist[i]] ++;
            }
        }
        cur = 0;
        for (int i = 0; i < nbRequetes; i ++)
        {
            while (cur <= min(maxi, Requetes[Ans[i].second]))
            {
                if (cur >= tailleCycle)
                    Occ[cur % tailleCycle] += Occ[cur];
                cur ++;
            }
            if (Requetes[Ans[i].second] % tailleCycle < MAX_ARETES)
                Ans[i].first += Occ[Requetes[Ans[i].second] % tailleCycle];
        }
    }
    for (int i = 0; i < nbRequetes; i ++)
    {
        swap(Ans[i].first, Ans[i].second);
    }
    sort(Ans, Ans + nbRequetes);
    for (int i = 0; i < nbRequetes; i ++)
    {
        answer(Ans[i].second);
    }
    return;
}

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