제출 #298428

#제출 시각아이디문제언어결과실행 시간메모리
298428Haunted_Cpp로봇 (IOI13_robots)C++17
39 / 100
283 ms65540 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; struct FlowEdge { int u, v; int cap, flow = 0; FlowEdge (int from, int to, long long w) : u (from), v (to), cap (w) {} }; struct EdmondsKarp { const int flow_inf = 1e9; vector<FlowEdge> edge; vector< vector<int> > g; vector<int> parent; int m, source, sink; EdmondsKarp (int n, int s, int t) : m(0), source (s), sink (t) { edge.clear(); g.clear(); g.resize(n); parent.clear(); parent.resize(n); } void reset(int n) { m = 0; edge.clear(); g.clear(); g.resize(n); parent.clear(); parent.resize(n); } void addEdge (int u, int v, int w) { edge.emplace_back(u, v, w); edge.emplace_back(v, u, 0); g[u].emplace_back(m); g[v].emplace_back(m + 1); m += 2; } int bfs () { fill (parent.begin(), parent.end(), -1); queue<pair<int, int > > q; q.push({source, flow_inf}); while (!q.empty()) { int node = q.front().first; int mn = q.front().second; q.pop(); if (node == sink) return mn; if (mn == 0) return 0; for (auto to : g[node]) { if (parent[edge[to].v] == -1 && edge[to].cap - edge[to].flow >= 1) { parent[edge[to].v] = to; q.push({edge[to].v, min (mn, edge[to].cap - edge[to].flow)}); } } } return 0; } int flow () { int f = 0; while (int add = bfs ()) { f += add; int cur = sink; while (cur != source) { int node = parent[cur]; edge[node].flow += add; edge[node ^ 1].flow -= add; cur = edge[parent[cur]].u; } } return f; } }; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { vector<int> weak, small; for (int i = 0; i < A; i++) { weak.emplace_back(X[i]); } for (int i = 0; i < B; i++) { small.emplace_back(Y[i]); } vector<pair<int, int>> arr(T); for (int i = 0; i < T; i++) { arr[i] = {W[i], S[i]}; } //~ sort(weak.begin(), weak.end()); //~ sort(small.begin(), small.end()); EdmondsKarp solve(T + A + B + 10, 0, 1); auto works = [&](int time) { solve.reset(T + A + B + 10); int cur = 2; for (int i = 0; i < A; i++) { solve.addEdge(0, cur, time); for (int j = 0; j < T; j++) { if (arr[j].first < X[i]) { solve.addEdge(cur, A + B + 5 + j, 1); } } ++cur; } for (int i = 0; i < B; i++) { solve.addEdge(0, cur, time); for (int j = 0; j < T; j++) { if (arr[j].second < Y[i]) { solve.addEdge(cur, A + B + 5 + j, 1); } } ++cur; } for (int j = 0; j < T; j++) { solve.addEdge(A + B + 5 + j, 1, 1); } return (solve.flow() == T); }; const int INF = 1e4 + 5; int lo = 0, hi = INF + 10; while(lo < hi) { const int mid = lo + (hi - lo) / 2; if (works(mid)) hi = mid; else lo = mid + 1; } return (hi > INF ? -1 : hi); }
#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...