Submission #838479

#	Time	Username	Problem	Language	Result	Execution time	Memory
838479		fatemetmhr	Fountain Parks (IOI21_parks)	C++17	100 / 100	1091 ms	78948 KiB

parks

// Be Name Khoda //
 
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
 
#include "parks.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)    x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi        first
#define se        second
#define pb        push_back
#define mp        make_pair
 
const int maxn5 = 1e6 + 10;
 
 
int n;
vector <int> ret[2], ed[2];
map <pair<int, int>, int> av, cnt, idof;
set <pair<pair<int, int>, pair<int, int>>> rem;


void dfs(int v, int x, int y){
    av.erase(mp(x, y));
    if(av.find(mp(x - 2, y)) != av.end()){
        int u = av[mp(x - 2, y)];
        dfs(u, x - 2, y);
    }
    if(av.find(mp(x + 2, y)) != av.end()){
        int u = av[mp(x + 2, y)];
        dfs(u, x + 2, y);
    }
    if(av.find(mp(x, y - 2)) != av.end()){
        int u = av[mp(x, y - 2)];
        dfs(u, x, y - 2);
    }
    if(av.find(mp(x, y + 2)) != av.end()){
        int u = av[mp(x, y + 2)];
        dfs(u, x, y + 2);
    }
}
 
 
int construct_roads(std::vector<int> x, std::vector<int> y) {

    n = x.size();

    for(int i = 0; i < n; i++)
        av[mp(x[i], y[i])] = i;
    dfs(0, x[0], y[0]);
    if(av.size())
        return 0;

    for(int i = 0; i < n; i++){
        cnt[mp(x[i] - 1, y[i] - 1)]++;
        cnt[mp(x[i] + 1, y[i] - 1)]++;
        cnt[mp(x[i] - 1, y[i] + 1)]++;
        cnt[mp(x[i] + 1, y[i] + 1)]++;
        idof[mp(x[i], y[i])] = i;
    }


    for(auto it = cnt.begin(); it != cnt.end(); it++) if(it -> se == 4){
        int x = (it -> fi).fi, y = (it -> fi).se;
        x--; y--;
        if(((x / 2) + (y / 2)) % 2){ // is black
            rem.insert({{x, y}, {x + 2, y}});
        }
        else{ // is white
            rem.insert({{x, y}, {x, y + 2}});
        }
    }

    for(int i = 0; i < n; i++){
        if(idof.find(mp(x[i] + 2, y[i])) != idof.end() &&
            rem.find(mp(mp(x[i], y[i]), mp(x[i] + 2, y[i]))) == rem.end()){
            ed[0].pb(i);
            ed[1].pb(idof[mp(x[i] + 2, y[i])]);
            ret[0].pb(x[i] + 1);
            if(((x[i] / 2) + (y[i] / 2)) % 2)
                ret[1].pb(y[i] + 1);
            else
                ret[1].pb(y[i] - 1);
        }

        if(idof.find(mp(x[i], y[i] + 2)) != idof.end() &&
            rem.find(mp(mp(x[i], y[i]), mp(x[i], y[i] + 2))) == rem.end()){
            ed[0].pb(i);
            ed[1].pb(idof[mp(x[i], y[i] + 2)]);
            ret[1].pb(y[i] + 1);
            if(((x[i] / 2) + (y[i] / 2)) % 2)
                ret[0].pb(x[i] - 1);
            else
                ret[0].pb(x[i] + 1);
        }
    }

    build(ed[0], ed[1], ret[0], ret[1]);
    return 1;
}
 
 
 
 
 
 
 
 
 
 
 
 

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