제출 #436005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436005		blue	분수 공원 (IOI21_parks)	C++17	15 / 100	283 ms	34688 KiB

parks

#include "parks.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

/*
For the vertical edges, use benches outside.
For the horizontal edges, use benches inside.
*/

vector<int> X, Y;
int N;

const int mx = 200000;

int construct_roads(vector<int> x, vector<int> y)
{
    X = x;
    Y = y;
    N = X.size();

    int fountain[5][1+mx];
    for(int i: vector<int>{2, 4})
        for(int j = 0; j <= mx; j++)
            fountain[i][j] = -1;

    for(int i = 0; i < N; i++)
    {
        fountain[ X[i] ][ Y[i] ] = i;
    }

    vector<int> U, V, A, B;

    vector<int> edge[N];
    for(int a = 2; a <= mx; a += 2)
    {
        if(a + 2 <= mx)
            for(int x1: vector<int>{2, 4})
            {
                if(fountain[x1][a] != -1 && fountain[x1][a+2] != -1)
                {
                    edge[ fountain[x1][a] ].push_back( fountain[x1][a+2] );
                    edge[ fountain[x1][a+2] ].push_back( fountain[x1][a] );

                    U.push_back(fountain[x1][a]);
                    V.push_back(fountain[x1][a+2]);
                    A.push_back(x1 == 2 ? 1 : 5);
                    B.push_back(a+1);
                }
            }

        if(fountain[2][a] != -1 && fountain[4][a] != -1)
        {
            edge[fountain[2][a]].push_back(fountain[4][a]);
            edge[fountain[4][a]].push_back(fountain[2][a]);

            U.push_back(fountain[2][a]);
            V.push_back(fountain[4][a]);
            A.push_back(3);
            B.push_back(a-1);
        }
    }



    queue<int> tbv;
    vector<int> visit(N, 0);
    tbv.push(0);
    visit[0] = 1;

    while(!tbv.empty())
    {
        int q = tbv.front();
        tbv.pop();

        for(int w: edge[q])
        {
            if(visit[w]) continue;
            visit[w] = 1;
            tbv.push(w);
        }
    }

    for(int i = 0; i < N; i++)
    {
        if(!visit[i]) return 0;
    }

    build(U, V, A, B);
    return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30