제출 #437975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437975		CyanForces	분수 공원 (IOI21_parks)	C++17	70 / 100	640 ms	70340 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=int(b); a<int(c); ++a)
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#pragma once

bool dfs(int a, int L, vector<vi>& g, vi& btoa, vi& A, vi& B) {
	if (A[a] != L) return 0;
	A[a] = -1;
	for (int b : g[a]) if (B[b] == L + 1) {
		B[b] = 0;
		if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
			return btoa[b] = a, 1;
	}
	return 0;
}

int hopcroftKarp(vector<vi>& g, vi& btoa) {
	int res = 0;
	vi A(g.size()), B(btoa.size()), cur, next;
	for (;;) {
		fill(all(A), 0);
		fill(all(B), 0);
		/// Find the starting nodes for BFS (i.e. layer 0).
		cur.clear();
		for (int a : btoa) if(a != -1) A[a] = -1;
		rep(a,0,sz(g)) if(A[a] == 0) cur.push_back(a);
		/// Find all layers using bfs.
		for (int lay = 1;; lay++) {
			bool islast = 0;
			next.clear();
			for (int a : cur) for (int b : g[a]) {
				if (btoa[b] == -1) {
					B[b] = lay;
					islast = 1;
				}
				else if (btoa[b] != a && !B[b]) {
					B[b] = lay;
					next.push_back(btoa[b]);
				}
			}
			if (islast) break;
			if (next.empty()) return res;
			for (int a : next) A[a] = lay;
			cur.swap(next);
		}
		/// Use DFS to scan for augmenting paths.
		rep(a,0,sz(g))
			res += dfs(a, 0, g, btoa, A, B);
	}
}

vector<int> parent;
vector<int> s;

int find(int x) {
  if(x==parent[x]) return x;
  else return parent[x]=find(parent[x]);
}

void makeset(int x) {
  parent[x]=x;
}

bool sameset(int x, int y) {
  return find(x)==find(y);
}

void join(int x, int y) {
  int xroot = find(x);
  int yroot = find(y);
  if(s[xroot]>s[yroot]) {
    parent[yroot]=xroot;
    s[xroot] += s[yroot];
  } else {
    parent[xroot]=yroot;
    s[yroot] += s[xroot];
  }
}

int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    int n = x.size();
    int M = 2*1e5+1;
    vector<vector<pair<int,int>>> x_fountains(M);
    vector<vector<pair<int,int>>> y_fountains(M);
    // first is the coordinate
    // second is the index.
    rep(i,0,n) {
      x_fountains[x[i]].emplace_back(y[i],i);
      y_fountains[y[i]].emplace_back(x[i],i);
    }
    rep(i,0,M) {
      sort(x_fountains[i].begin(), x_fountains[i].end());
      sort(y_fountains[i].begin(), y_fountains[i].end());
    }

    vector<int> u, v, a, b;

    parent.clear();
    parent.resize(n);
    s.resize(n);
    rep(i,0,n) makeset(i);
    rep(i,0,M) {
      rep(j,1,x_fountains[i].size()) {
        int ind1 = x_fountains[i][j-1].second;
        int y1 = x_fountains[i][j-1].first;
        int ind2 = x_fountains[i][j].second;
        int y2 = x_fountains[i][j].first;
        if(y2-y1!=2) continue;
        if(sameset(ind1,ind2)) continue;
        join(ind1,ind2);
        u.push_back(ind1);
        v.push_back(ind2);
      }
    }
    rep(i,0,M) {
      rep(j,1,y_fountains[i].size()) {
        int ind1 = y_fountains[i][j-1].second;
        int x1 = y_fountains[i][j-1].first;
        int ind2 = y_fountains[i][j].second;
        int x2 = y_fountains[i][j].first;
        if(x2-x1!=2) continue;
        if(sameset(ind1,ind2)) continue;
        join(ind1,ind2);
        u.push_back(ind1);
        v.push_back(ind2);
      }
    }
    int num_roads = u.size();
    if(num_roads!=n-1) return 0;
    map<pair<int,int>, int> potential_benches;
    vector<pair<int,int>> potential_benches2;
    vector<vector<int>> graph(num_roads);
    rep(i,0,num_roads) {
      int f1 = u[i];
      int f2 = v[i];
      vector<pair<int,int>> temp;
      if(x[f1]==x[f2]) {
        int mid = (y[f1]+y[f2])/2;
        temp.emplace_back(x[f1]-1, mid);
        temp.emplace_back(x[f1]+1, mid);
      } else {
        assert(y[f1]==y[f2]);
          int mid = (x[f1]+x[f2])/2;
          temp.emplace_back(mid, y[f1]-1);
          temp.emplace_back(mid, y[f1]+1);
      }
      rep(j,0,temp.size()) {
        if (!potential_benches.count(temp[j])) {
          potential_benches[temp[j]]=potential_benches.size();
          potential_benches2.emplace_back(temp[j]);
        }
        graph[i].push_back(potential_benches[temp[j]]);
      }
    }
    vector<int> btoa(potential_benches.size(),-1);
    hopcroftKarp(graph, btoa);
    a.resize(num_roads);
    b.resize(num_roads);
    rep(i,0,potential_benches2.size()) {
      if(btoa[i] != -1) {
        a[btoa[i]] = potential_benches2[i].first;
        b[btoa[i]] = potential_benches2[i].second;
      }
    }
    build(u, v, a, b);
    return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

parks.cpp:11:9: warning: #pragma once in main file
   11 | #pragma once
      |         ^~~~

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