Submission #57598

#TimeUsernameProblemLanguageResultExecution timeMemory
57598polyfishPriglavci (COCI18_priglavci)C++14
16 / 160
8 ms1208 KiB
//I love armpit fetish #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "data" #define x first #define y second typedef pair<int, int> point; const int MAX_N = 102; const int INF = 1e9; int n, m, bus_capacity, nBus, c[MAX_N][MAX_N], f[MAX_N][MAX_N]; int source, target, d[MAX_N], nTime, visited[MAX_N]; vector<int> bus[MAX_N], g[MAX_N]; point bus_stop[MAX_N], student[MAX_N]; int sqr(int x) { return x * x; } int dist(point p, point q) { return sqr(p.x - q.x) + sqr(p.y - q.y); } int dist(int bus_id, point s) { int res = INF; for (int i=0; i<bus[bus_id].size(); ++i) { int u = bus[bus_id][i]; res = min(res, dist(bus_stop[u], s)); } return res; } void enter() { cin >> n >> m >> bus_capacity >> nBus; for (int i=1; i<=n; ++i) cin >> student[i].x >> student[i].y; for (int i=1; i<=m; ++i) cin >> bus_stop[i].x >> bus_stop[i].y; for (int i=1; i<=nBus; ++i) { int k; cin >> k; while (k--) { int x; cin >> x; bus[i].push_back(x); } } } void init_graph(int weakness) { source = 1; target = nBus + n + 2; for (int i=source; i<=target; ++i) g[i].clear(); memset(c, 0, sizeof(c)); memset(f, 0, sizeof(f)); for (int i=2; i<=nBus+1; ++i) { g[source].push_back(i); g[i].push_back(source); c[source][i] = bus_capacity; } for (int i=nBus+2; i<=nBus+n+1; ++i) { g[target].push_back(i); g[i].push_back(target); c[i][target] = 1; } for (int i=1; i<=nBus; ++i) { for (int j=1; j<=n; ++j) { if (dist(i, student[j])<=weakness) { g[i+1].push_back(j+nBus+1); g[j+nBus+1].push_back(i+1); c[i+1][j+nBus+1] = 1; } } } } bool bfs() { memset(d, 0, sizeof(d)); d[source] = 1; queue<int> qu; qu.push(source); while (qu.size()) { int u = qu.front(); qu.pop(); if (u==target) return true; for (int i=0; i<g[u].size(); ++i) { int v = g[u][i]; if (d[v]==0 && c[u][v]>f[u][v]) { d[v] = d[u] + 1; qu.push(v); } } } return false; } int find_path(int u, int delta) { if (visited[u] != nTime) visited[u] = nTime; else return 0; if (u==target) return delta; for (int i=0; i<g[u].size(); ++i) { int v = g[u][i]; if (d[v]==d[u] + 1 && c[u][v]>f[u][v]) { int x = find_path(v, min(delta, c[u][v]-f[u][v])); if (x>0) { f[u][v] += x; f[v][u] -= x; return x; } } } return 0; } int max_flow(int weakness) { init_graph(weakness); // PR0(g[3], g[3].size()); // debug(c[4][5]); int res = 0; while (bfs()) { while (true) { ++nTime; int x = find_path(source, INF); if (x==0) break; res += x; //assert(res<=n); } } return res; } int bisect() { int l = 0, r = INF, mid = (l + r) / 2; while (l!=mid && mid!=r) { if (max_flow(mid) == n) r = mid; else l = mid; mid = (l + r) / 2; } for (int i=l; i<=r; ++i) if (max_flow(i) == n) return i; } void trace() { for (int i=nBus+2; i<=nBus+n+1; ++i) { for (int j=2; j<=nBus+1; ++j) { if (f[j][i]==1) { cout << j-1 << '\n'; break; } } } } int main() { //#define OFFLINE_JUDGE doraemon #ifdef OFFLINE_JUDGE freopen(FILE_NAME".inp", "r", stdin); freopen(FILE_NAME".out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); enter(); if (bus_capacity * nBus < n) { cout << -1; return 0; } //debug(max_flow(4)); cout << bisect() << '\n'; trace(); }

Compilation message (stderr)

priglvaci.cpp: In function 'int dist(int, point)':
priglvaci.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<bus[bus_id].size(); ++i) {
                ~^~~~~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'bool bfs()':
priglvaci.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<g[u].size(); ++i) {
                 ~^~~~~~~~~~~~
priglvaci.cpp: In function 'int find_path(int, int)':
priglvaci.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
priglvaci.cpp: In function 'int bisect()':
priglvaci.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...