제출 #1198677

#제출 시각아이디문제언어결과실행 시간메모리
1198677Mher777자매 도시 (APIO20_swap)C++17
100 / 100
155 ms25924 KiB
#include "swap.h" #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <iomanip> #include <array> #include <string> #include <algorithm> #include <cmath> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <vector> #include <stack> #include <queue> #include <deque> #include <bitset> #include <list> #include <iterator> #include <numeric> #include <complex> #include <utility> #include <random> #include <cassert> #include <fstream> using namespace std; mt19937 rnd(7069); typedef int itn; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef float fl; typedef long double ld; using vi = vector<int>; using vll = vector<ll>; using mii = map<int, int>; using mll = map<ll, ll>; using pii = pair<int, int>; using pll = pair<ll, ll>; #define ff first #define ss second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define mpr make_pair #define yes cout<<"Yes\n" #define no cout<<"No\n" #define all(x) (x).begin(), (x).end() const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 }; const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 }; const int MAX = int(1e9 + 5); const ll MAXL = ll(1e18) + 5ll; const ll MOD = ll(1000000007); const ll MOD2 = ll(998244353); const int max_N = 100005; vector<pair<int,pii>> inf[max_N]; vi g[max_N]; int sz[max_N], p[max_N], type[max_N], adj_cnt[max_N]; int n, m, timer; vector<pair<int, pii>> edges = { {0,{0,0}} }; void make_set(int x) { g[x] = { x }; p[x] = x; sz[x] = 1; } int find_set(int x) { if (p[x] == x) return x; return p[x] = find_set(p[x]); } void fill_information(int set_index, int new_set) { for (auto node : g[set_index]) { inf[node].pub({ timer,{ new_set,type[new_set] }}); } } void union_sets(int x, int y, int w) { ++adj_cnt[x]; ++adj_cnt[y]; int x_set = find_set(x), y_set = find_set(y); if (x_set == y_set) { if (type[x_set]) return; type[x_set] = w; fill_information(x_set, x_set); return; } if (sz[x_set] < sz[y_set]) { swap(x_set, y_set); } sz[x_set] += sz[y_set]; p[y_set] = x_set; if (!type[x_set] && (type[y_set] || adj_cnt[x] >= 3 || adj_cnt[y] >= 3)) { type[x_set] = w; fill_information(x_set, x_set); } for (auto node : g[y_set]) { g[x_set].pub(node); } if (!type[x_set]) return; type[x_set] = w; fill_information(y_set, x_set); } void init(int N, int M, vi U, vi V, vi W) { n = N, m = M; for (int i = 0; i < n; ++i) { make_set(i); } for (int i = 0; i < m; ++i) { edges.pub({ W[i],{U[i],V[i]} }); } sort(all(edges)); for (auto opt : edges) { if (opt.ff == 0) continue; ++timer; int x = opt.ss.ff; int y = opt.ss.ss; int w = opt.ff; union_sets(x, y, w); } } int find_minimum(int x, int y) { int ret = MAX; for (auto opt1 : inf[x]) { for (auto opt2 : inf[y]) { int set_x = opt1.ss.ff; int set_y = opt2.ss.ff; if (set_x != set_y) continue; ret = min(ret, max(opt1.ss.ss,opt2.ss.ss)); } } return ret; /*int l = 0, r = (int)inf[x].size() - 1, mid; int ret = MAX; while (l <= r) { mid = (l + r) / 2; int jam = inf[x][mid].ff; int x_set = inf[x][mid].ss; int ind = lower_bound(all(inf[y]), mpr(inf[x][mid].ff, -1)) - inf[y].begin() - 1; if (ind >= 0 && ind < (int)inf[y].size() && inf[y][ind].ss == x_set) { ret = min(ret, max(edges[jam].ff, edges[inf[y][mid].ff].ff)); r = mid - 1; continue; } ++ind; if (ind >= 0 && ind < (int)inf[y].size() && inf[y][ind].ss == x_set) { ret = min(ret, max(edges[jam].ff, edges[inf[y][mid].ff].ff)); r = mid - 1; continue; } l = mid + 1; } return ret;*/ } int getMinimumFuelCapacity(int X, int Y) { int x = X, y = Y; int ans = min(find_minimum(x, y), find_minimum(y, x)); return (ans == MAX ? -1 : ans); } /* 5 6 0 1 4 0 2 4 1 2 1 1 3 2 1 4 10 2 3 3 3 1 2 2 4 0 1 */ /* 3 2 0 1 5 0 2 5 1 1 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...