제출 #237434

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

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define DIM 300010
#define INF 2000000000
using namespace std;

int nxt[DIM],dist[DIM],dist2[DIM];
vector <pair<int,int> > L[DIM];
vector <int> edg[DIM];
deque <int> c;

/*void answer (int n){
    cout<<n<<"\n";
}*/

void bfs (int start, int n, int dist[]){
    int i;
    for (i=1;i<=2*n;i++)
        dist[i] = INF;

    c.clear();
    c.push_back(start);
    dist[start] = 0;

    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        for (auto vecin : edg[nod]){
            if (dist[vecin] == INF){
                dist[vecin] = 1 + dist[nod];
                c.push_back(vecin);
            }}}}

void count_routes (int n, int m, int dest, int r[][2], int q, int g[]){

    int i,j;
    for (i=0;i<m;i++){
        int x = r[i][0] + 1, y = r[i][1] + 1;
        L[x].push_back(make_pair(i,y));
        L[y].push_back(make_pair(i,x));
    }
    dest++;

    for (i=1;i<=n;i++)
        sort (L[i].begin(),L[i].end());

    for (i=1;i<=n;i++){

        /// duc muchia catre cea mai buna varianta

        j = L[i][0].second;
        if (L[j][0].second != i){
            edg[j].push_back(i); /// graful o sa fie pe invers
            nxt[i] = j;
        } else {
            edg[j+n].push_back(i);
            nxt[i] = j+n;
        }
        /// a doua muchie
        if (L[i].size() >= 2){
            j = L[i][1].second;
            if (L[j][0].second != i){
                edg[j].push_back(i+n);
                nxt[i+n] = j;
            } else {
                edg[j+n].push_back(i+n);
                nxt[i+n] = j+n;
            }
        } else {
            j = L[i][0].second;
            if (L[j][0].second != i){
                edg[j].push_back(i+n);
                nxt[i+n] = j;
            } else {
                edg[j+n].push_back(i+n);
                nxt[i+n] = j+n;
            }}}

    bfs (dest,n,dist);
    bfs (dest+n,n,dist2);

    //for (i=1;i<=2*n;i++)
       // cout<<dist[i]<<"\n";

    /// am doua variante de a ajunge la destinatie => doua cicluri posibile

    int lg = dist[nxt[dest]] + 1;
    int lg2 = dist2[nxt[dest+n]] + 1;

    for (i=0;i<q;i++){
        int k = g[i], sol = 0;
        for (j=1;j<=n;j++)
            if ( ((k >= dist[j]) && (k - dist[j]) % lg == 0) || (k >= dist2[j] && (k - dist2[j]) % lg2 == 0) )
                sol++;

        answer(sol);
    }

}

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