Submission #238741

#	Time	Username	Problem	Language	Result	Execution time	Memory
238741		Nightlight	Priglavci (COCI18_priglavci)	C++14	160 / 160	16 ms	640 KiB

priglvaci

#include <bits/stdc++.h>
#define ABS(n) ((n) > 0 ? (n) : -(n))
#define pii pair<int, int>
using namespace std;

int N, M, C, K;
pii A[105];
pii B[105];
vector<int> bus[105];
//for macflow
vector<int> adj[205];
int cap[205][205];
int par[205];

int dist(int a, int b, int x, int y) {
  return ABS(a - x) * ABS(a - x) + ABS(b - y) * ABS(b - y);
}

void edge(int u, int v, int c) {
  cap[u][v] = c;
  adj[u].push_back(v);
  adj[v].push_back(u);
}

int bfs() {
  memset(par, -1, sizeof(par));
  queue<pii> q;
  par[0] = -2;
  q.emplace(0, 1000000);
  while(!q.empty()) {
    int u = q.front().first;
    int flow = q.front().second;
    q.pop();

    for(int v : adj[u]) {
      if(par[v] == -1 && cap[u][v]) {
        par[v] = u;
        int new_flow = min(flow, cap[u][v]);
        if(v == 201) return new_flow;
        q.emplace(v, new_flow);
      }
    }
  }
  return 0;
}

int maxflow() {
  int flow = 0, new_flow;
  while(new_flow = bfs()) {
    flow += new_flow;
    int u = 201;
    while(u != 0) {
      cap[par[u]][u] -= new_flow;
      cap[u][par[u]] += new_flow;
      u = par[u];
    }
  }
  return flow;
}

void clear() {
  memset(cap, 0, sizeof(cap));
  adj[0].clear(), adj[201].clear();
  for(int i = 1; i <= N; i++) {
    adj[i].clear();
    edge(0, i, 1);
  }
  for(int i = 1; i <= K; i++) {
    adj[100 + i].clear();
    edge(100 + i, 201, C);
  }
}

void prepare(int mac) {
  clear();
  bool ok;
//  cout << mac << "\n";
  for(int i = 1; i <= N; i++) {
    pii u = A[i];
    for(int j = 1; j <= K; j++) {
      ok = 0;
      for(int now : bus[j]) {
        pii v = B[now];
        if(dist(u.first, u.second, v.first, v.second) <= mac) {
          ok = 1;
          break;
        }
      }
      if(ok) {
//        cout << i << " " << j << "\n";
        edge(i, 100 + j, 1);
      }
    }
  }
}

bool check(int mid) {
  prepare(mid);
  int res = maxflow();
//  cout << mid << " " << res << "\n";
  return res == N;
}
bool vis[205];

void binser() {
  int l = 0, r = 2000000, res = 2000000;
  while(l <= r) {
    int mid = (l + r) >> 1;
    if(check(mid)) {
      r = mid - 1;
      res = mid;
    }else l = mid + 1;
  }
  check(res);
  printf("%d\n", res);
  for(int i = 1; i <= N; i++) {
    pii u = A[i];
    for(int j = 1; j <= K; j++) {
      if(cap[j + 100][i]) {
        for(int now : bus[j]) {
          pii v = B[now];
          if(vis[now]) continue;
          if(dist(u.first, u.second, v.first, v.second) <= res) {
            printf("%d\n", now);
            break;
          }
        }
        break;
      }
    }
  }
}

void input() {
  scanf("%d %d %d %d", &N, &M, &C, &K);
  if(K * C < N) {
    puts("-1");
    exit(0);
  }
  int x, y, sz;
  for(int i = 1; i <= N; i++) {
    scanf("%d %d", &x, &y);
    A[i] = make_pair(x, y);
  }
  for(int i = 1; i <= M; i++) {
    scanf("%d %d", &x, &y);
    B[i] = make_pair(x, y);
  }
  for(int i = 1; i <= K; i++) {
    scanf("%d", &sz);
    while(sz--) {
      scanf("%d", &x);
      bus[i].push_back(x);
    }
  }
}

int main() {
  input();
  binser();
  cin >> N;
}

Compilation message (stderr)

priglvaci.cpp: In function 'int maxflow()':
priglvaci.cpp:49:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   while(new_flow = bfs()) {
         ~~~~~~~~~^~~~~~~
priglvaci.cpp: In function 'void input()':
priglvaci.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &N, &M, &C, &K);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~
priglvaci.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~
priglvaci.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &sz);
     ~~~~~^~~~~~~~~~~
priglvaci.cpp:152:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &x);
       ~~~~~^~~~~~~~~~

• Subtask 1: 160 / 160