Submission #240018

#	Time	Username	Problem	Language	Result	Execution time	Memory
240018		maximath_1	Priglavci (COCI18_priglavci)	C++11	160 / 160	17 ms	768 KiB

priglvaci

#include<bits/stdc++.h>
using namespace std;
const int inf=2e6;
int n, m, c, k;
pair<int, int>u[105], s[105];
vector<int>bus[105], adj[105*2];
int cap[105*2][105*2], par[105*2];
int dst(pair<int, int>A, pair<int, int>B){return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);}
int bfs(){
	memset(par, -1, sizeof(par));
	par[0]=-inf;
	queue<pair<int, int> >q;
	q.push({0, inf}); //source cap inf
	for(;!q.empty();q.pop()){
		int nw=q.front().first, flw=q.front().second;
		for(int nx:adj[nw]) if(par[nx]==-1 && cap[nw][nx]){
			par[nx]=nw;
			int nflw=min(flw, cap[nw][nx]);
			if(nx==201) return nflw; //sink reached
			q.push({nx, nflw});
		}
	}
	return 0;
}
int maxflow(){
	int mxflw=0, nflw=0;
	for(nflw=bfs(); nflw!=0; nflw=bfs()){
		mxflw+=nflw;
		int nw=201; //retrace path from sink
		for(;nw!=0;nw=par[nw]){
			cap[par[nw]][nw]-=nflw;
			cap[nw][par[nw]]+=nflw; //backedge
		}
	}
	return mxflw;
}
void addedge(int u, int v, int c){
	cap[u][v]=c;
	adj[u].push_back(v); adj[v].push_back(u);
}
void reset(int lim){
	memset(cap, 0, sizeof(cap));
	adj[0].clear(); adj[201].clear();
	for(int i=1; i<=n; i++)
		adj[i].clear(), addedge(0, i, 1);
	for(int i=1; i<=k; i++)
		adj[100+i].clear(), addedge(100+i, 201, c);
	bool kk;
	for(int i=1; i<=n; i++){
		pair<int, int>nw=u[i];
		for(int j=1; j<=k; j++){
			kk=false;
			for(int nex:bus[j]){
				pair<int, int>nx=s[nex];
				if(dst(nw, nx)<=lim)
					{kk=true; break;}
			}
			if(kk)
				addedge(i, 100+j, 1);
		}
	}
}
bitset<205>vis;
int main(){
	scanf("%d%d%d%d", &n, &m, &c, &k);
	for(int i=1; i<=n; i++)
		scanf("%d%d", &u[i].first, &u[i].second);
	for(int i=1; i<=m; i++)
		scanf("%d%d", &s[i].first, &s[i].second);
	for(int sz, i=1; i<=k; i++){
		scanf("%d", &sz);
		for(int j=0, x; j<sz; j++){
			scanf("%d", &x);
			bus[i].push_back(x);
		}
	}
	int l=0, r=inf, res=inf;
	for(int md=(l+r)/2; l<=r; md=(l+r)/2){
		reset(md);
		int mxflow=maxflow();
		if(mxflow==n)
			res=md, r=md-1;
		else l=md+1;
	}
	reset(res);
	int getmxflw=maxflow();
	if(getmxflw!=n){
		printf("-1\n");
		return 0;
	}
	printf("%d\n", res);
	for(int i=1; i<=n; i++){
		pair<int, int>nw=u[i];
		for(int j=1; j<=k; j++) if(cap[j+100][i]){
			for(int nex:bus[j]){
				pair<int, int>nx=s[nex];
				if(vis[nex]) continue;
				if(dst(nw, nx)<=res){
					printf("%d\n", nex);
					break;
				}
			}break;
		}
	}
	return 0;
}

Compilation message (stderr)

priglvaci.cpp: In function 'int main()':
priglvaci.cpp:65:7: 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:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u[i].first, &u[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s[i].first, &s[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &sz);
   ~~~~~^~~~~~~~~~~
priglvaci.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~

• Subtask 1: 160 / 160