Submission #990900

#	Time	Username	Problem	Language	Result	Execution time	Memory
990900		AdamGS	Fountain Parks (IOI21_parks)	C++17	100 / 100	425 ms	46012 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
int F[LIM], n, dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
map<pair<int,int>,int>mp, odw;
int fnd(int x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
bool uni(int a, int b) {
  if(fnd(a)==fnd(b)) return false;
  F[fnd(b)]=fnd(a);
  return true;
}
int construct_roads(vector<int>x, vector<int>y) {
  n=x.size();
  rep(i, n) mp[{x[i], y[i]}]=i;
  rep(i, n) F[i]=i;
  vector<pair<int,pair<int,int>>>V;
  vector<int>u, v, a, b;
  rep(i, n) if(mp.find({x[i], y[i]+2})!=mp.end()) V.pb({x[i], {i, mp[{x[i], y[i]+2}]}});
  sort(all(V));
  for(auto i : V) {
    pair<int,int>p={x[i.nd.st], y[i.nd.st]+1};
    if(abs((p.st+p.nd+1)/2)%2==0) ++p.st; else --p.st;
    if(odw[p]) continue;
    if(uni(i.nd.st, i.nd.nd)) {
      u.pb(i.nd.st);
      v.pb(i.nd.nd);
      a.pb(p.st);
      b.pb(p.nd);
      odw[p]=1;
    }
  }
  V.clear();
  rep(i, n) if(mp.find({x[i]+2, y[i]})!=mp.end()) V.pb({y[i], {i, mp[{x[i]+2, y[i]}]}});
  sort(all(V));
  for(auto i : V) {
    pair<int,int>p={x[i.nd.st]+1, y[i.nd.st]};
    if(abs((p.st+p.nd+1)/2)%2==1) ++p.nd; else --p.nd;
    if(odw[p]) continue;
    if(uni(i.nd.st, i.nd.nd)) {
      u.pb(i.nd.st);
      v.pb(i.nd.nd);
      a.pb(p.st);
      b.pb(p.nd);
      odw[p]=1;
    }
  }
  rep(i, n) if(fnd(i)!=fnd(0)) return 0;
  build(u, v, a, b);
  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