Submission #1030845
Source Code Expand
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
using namespace std;
#ifdef DEB
#define dump(x) cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;
namespace std{
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.fr<<','<<a.sc<<')';
return out;
}
}
const double INF=1e10;
int n;
pi ps[20];
double d[20][20];
int ar[20];
double sq(double a){
return a*a;
}
struct uf{
static const int MAXN=18;
int par[MAXN];
int size[MAXN];
void init(){
memset(par,-1,sizeof(par));
REP(i,MAXN) size[i]=1;
}
int root(int a){
if(par[a]==-1) return a;
return par[a]=root(par[a]);
}
void unite(int a,int b){
a=root(a);b=root(b);
if(a==b) return;
if(size[a]<size[b]) swap(a,b);
par[b]=a;
size[a]+=size[b];
}
bool same(int a,int b){
return root(a)==root(b);
}
};
uf u;
vector<int> g[20];
pair<double,pi> es[150];
double dfs(int v,int p,double thr){
double cur=ar[v];
for(auto to:g[v]){
if(to==p) continue;
double a=dfs(to,v,thr);
if(a>0){
cur-=d[v][to]+a;
}else{
cur+=max(0.0,-a-d[v][to]);
}
}
return -(cur-thr);
}
bool check(double thr,int r){
double req=dfs(r,-1,thr);
if(req<=0) return true;
return false;
}
double calc(int bit){
int m=0;
int r=-1;
REP(i,n) g[i].clear();
REP(i,n) if(bit>>i&1){
REP(j,i) if(bit>>j&1){
es[m++]=mp(d[i][j],mp(i,j));
}
r=i;
}
sort(es,es+m);
u.init();
REP(i,m){
int a=es[i].sc.fr,b=es[i].sc.sc;
if(!u.same(a,b)){
u.unite(a,b);
g[a].pb(b);
g[b].pb(a);
}
}
double lb=0,ub=1e9+10;
REP(i,100){
double md=(lb+ub)/2;
if(check(md,r)) lb=md;
else ub=md;
}
return lb;
}
double wat[1<<15];
double dp[1<<15];
int main(){
cin>>n;
REP(i,n){
cin>>ps[i].fr>>ps[i].sc>>ar[i];
}
REP(i,n) REP(j,n) {
d[i][j]=sqrt(sq(ps[i].fr-ps[j].fr)+sq(ps[i].sc-ps[j].sc));
}
REP(i,1<<n) if(i>0){
wat[i]=calc(i);
}
dp[0]=INF;
for(int i=1;i<(1<<n);++i){
int cur=i;
do{
chmax(dp[i],min(wat[cur],dp[i^cur]));
cur=(cur-1)&i;
}while(cur>0);
}
printf("%.10f\n",dp[(1<<n)-1]);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Water Distribution |
User |
hogloid |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
3218 Byte |
Status |
AC |
Exec Time |
265 ms |
Memory |
768 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, example0.txt, example1.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
240 ms |
768 KB |
001.txt |
AC |
252 ms |
768 KB |
002.txt |
AC |
243 ms |
768 KB |
003.txt |
AC |
244 ms |
768 KB |
004.txt |
AC |
246 ms |
768 KB |
005.txt |
AC |
245 ms |
768 KB |
006.txt |
AC |
250 ms |
768 KB |
007.txt |
AC |
245 ms |
768 KB |
008.txt |
AC |
238 ms |
768 KB |
009.txt |
AC |
239 ms |
768 KB |
010.txt |
AC |
233 ms |
768 KB |
011.txt |
AC |
240 ms |
768 KB |
012.txt |
AC |
238 ms |
768 KB |
013.txt |
AC |
245 ms |
768 KB |
014.txt |
AC |
246 ms |
768 KB |
015.txt |
AC |
238 ms |
768 KB |
016.txt |
AC |
251 ms |
768 KB |
017.txt |
AC |
239 ms |
768 KB |
018.txt |
AC |
245 ms |
768 KB |
019.txt |
AC |
236 ms |
768 KB |
020.txt |
AC |
250 ms |
768 KB |
021.txt |
AC |
253 ms |
768 KB |
022.txt |
AC |
244 ms |
768 KB |
023.txt |
AC |
259 ms |
768 KB |
024.txt |
AC |
243 ms |
768 KB |
025.txt |
AC |
249 ms |
768 KB |
026.txt |
AC |
254 ms |
768 KB |
027.txt |
AC |
255 ms |
768 KB |
028.txt |
AC |
262 ms |
768 KB |
029.txt |
AC |
256 ms |
768 KB |
030.txt |
AC |
258 ms |
768 KB |
031.txt |
AC |
264 ms |
768 KB |
032.txt |
AC |
254 ms |
768 KB |
033.txt |
AC |
261 ms |
768 KB |
034.txt |
AC |
259 ms |
768 KB |
035.txt |
AC |
256 ms |
768 KB |
036.txt |
AC |
260 ms |
768 KB |
037.txt |
AC |
248 ms |
768 KB |
038.txt |
AC |
253 ms |
768 KB |
039.txt |
AC |
265 ms |
768 KB |
040.txt |
AC |
3 ms |
256 KB |
041.txt |
AC |
3 ms |
256 KB |
042.txt |
AC |
3 ms |
256 KB |
043.txt |
AC |
3 ms |
256 KB |
example0.txt |
AC |
3 ms |
256 KB |
example1.txt |
AC |
249 ms |
768 KB |