Submission #496135

#	Time	Username	Problem	Language	Result	Execution time	Memory
496135		Half	Fountain Parks (IOI21_parks)	C++17	15 / 100	167 ms	18952 KiB

parks

#include "parks.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"DEBUG "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

int construct_roads(std::vector<int> ax, std::vector<int> ay) {
    int n = ax.size();
    std::vector<int> u, v, a, b;
    int grd[3][100007];
    memset(grd, 0, sizeof grd);
    for(int i = 0; i < n; i++){
        grd[ax[i]/2][ay[i]/2] = i+1;
        grd[0][ay[i]/2] += 1<<(ax[i]/2 - 1);
    }
    bool grp = false;
    for(int y = 1; y < 100007; y++){
        if(grd[0][y] && !grd[0][y-1] && grp)
            return 0;
        if(!grd[0][y])
            continue;
        grp = true;
        if(grd[1][y] && grd[1][y-1]){
            u.pb(grd[1][y]-1);
            v.pb(grd[1][y-1]-1);
            a.pb(1);
            b.pb(2*y-1);
        }
        if(grd[2][y] && grd[2][y-1]){
            u.pb(grd[2][y]-1);
            v.pb(grd[2][y-1]-1);
            a.pb(5);
            b.pb(2*y-1);
        }
        if(grd[1][y] && grd[2][y]){
            u.pb(grd[1][y]-1);
            v.pb(grd[2][y]-1);
            a.pb(3);
            b.pb(2*y-1);
        }
        if(grd[0][y] == 1 && grd[0][y-1] == 2)
            return 0;
        if(grd[0][y] == 2 && grd[0][y-1] == 1)
            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