Submission #1339069
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
using pi = pair<int,int>;
// (行き先, 容量, コスト, 逆辺)
struct edge{ int to,cap,cost,rev; };
int V; // TODO:initialize
const int MAX_V = 2500; // TODO:initialize
const int INF = 123456789; // TODO:initialize
vector<edge> G[MAX_V];
int h[MAX_V]; // ポテンシャル
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V]; // 直前の頂点と辺
void add_edge(int from, int to, int cap, int cost){
G[from].pb({to,cap,cost,G[to].size()});
G[to].pb({from,0,-cost,G[from].size()-1});
}
// sからtへの流量fの最小費用流(不可能なら-1)
int min_cost_flow(int s, int t, int f){
int res = 0;
fill(h,h+V,0);
while(f>0){
// dijkstraでhを更新
priority_queue<pi,vector<pi>,greater<pi>> pq;
fill(dist,dist+V,INF);
dist[s]=0;
pq.push(pi(0,s));
while(!pq.empty()){
pi p = pq.top();
pq.pop();
int v = p.se;
if(p.fi>dist[v]) continue;
rep(i,G[v].size()){
edge &e = G[v][i];
if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
pq.push(pi(dist[e.to],e.to));
}
}
}
// これ以上流せない
if(dist[t]==INF) return -1;
rep(v,V) h[v] += dist[v];
// s-t間の最短路に沿って目一杯流す
int d=f;
for(int v=t; v!=s; v=prevv[v]) d = min(d,G[prevv[v]][preve[v]].cap);
f -= d;
res += d*h[t];
for(int v=t; v!=s; v=prevv[v]){
edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return res;
}
struct Point{ int x,y; };
const int C=10;
int m,n;
Point r[3],p[1000];
int s[1000],t[1000];
inline int d2(Point a, Point b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int main()
{
scanf(" %d", &m);
rep(i,m) scanf(" %d %d", &r[i].x, &r[i].y);
scanf(" %d", &n);
rep(i,n) scanf(" %d %d %d %d", &p[i].x, &p[i].y, &s[i], &t[i]);
V = 2*n + m + 2;
int S = 2*n, T = 2*n+1;
vector<int> M(m);
rep(i,m) M[i] = 2*n+2+i;
rep(i,m)
{
add_edge(S,M[i],1,0);
add_edge(M[i],T,1,0);
}
rep(i,n)
{
add_edge(2*i,2*i+1,1,-C);
add_edge(2*i+1,T,1,0);
}
rep(i,m)rep(j,n)
{
if(d2(r[i],p[j]) <= s[j]*s[j]) add_edge(M[i],2*j,1,0);
}
rep(i,n)for(int j=i+1; j<n; ++j)
{
if(d2(p[i],p[j]) <= (s[j]-t[i])*(s[j]-t[i])) add_edge(2*i+1,2*j,1,0);
}
printf("%s\n", (min_cost_flow(S,T,m)==-C*n)?"YES":"NO");
return 0;
}
Submission Info
Submission Time |
|
Task |
D - ラボライブ タフグローバルフェスティバル |
User |
imulan |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
3367 Byte |
Status |
AC |
Exec Time |
98 ms |
Memory |
26864 KB |
Compile Error
./Main.cpp: In function ‘void add_edge(int, int, int, int)’:
./Main.cpp:27:39: warning: narrowing conversion of ‘G[to].std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >()’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘int’ inside { } [-Wnarrowing]
G[from].pb({to,cap,cost,G[to].size()});
^
./Main.cpp:28:42: warning: narrowing conversion of ‘(G[from].std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >() + 18446744073709551615ul)’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘int’ inside { } [-Wnarrowing]
G[to].pb({from,0,-cost,G[from].size()-1});
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:92:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d", &m);
^
./Main.cpp:93:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared wit...
Judge Result
Set Name |
All |
Score / Max Score |
200 / 200 |
Status |
|
Set Name |
Test Cases |
All |
scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, scrambled_33.txt, scrambled_34.txt, scrambled_35.txt, scrambled_36.txt, scrambled_37.txt, scrambled_38.txt, scrambled_39.txt, scrambled_40.txt, scrambled_41.txt, scrambled_42.txt, scrambled_43.txt, scrambled_44.txt, scrambled_45.txt, scrambled_46.txt, scrambled_47.txt, scrambled_48.txt, scrambled_49.txt, scrambled_50.txt, scrambled_51.txt, scrambled_52.txt, scrambled_53.txt |
Case Name |
Status |
Exec Time |
Memory |
scrambled_00.txt |
AC |
1 ms |
384 KB |
scrambled_01.txt |
AC |
1 ms |
384 KB |
scrambled_02.txt |
AC |
1 ms |
384 KB |
scrambled_03.txt |
AC |
98 ms |
25044 KB |
scrambled_04.txt |
AC |
97 ms |
25168 KB |
scrambled_05.txt |
AC |
98 ms |
24916 KB |
scrambled_06.txt |
AC |
87 ms |
25848 KB |
scrambled_07.txt |
AC |
88 ms |
26864 KB |
scrambled_08.txt |
AC |
1 ms |
384 KB |
scrambled_09.txt |
AC |
1 ms |
384 KB |
scrambled_10.txt |
AC |
1 ms |
384 KB |
scrambled_11.txt |
AC |
1 ms |
384 KB |
scrambled_12.txt |
AC |
1 ms |
384 KB |
scrambled_13.txt |
AC |
1 ms |
384 KB |
scrambled_14.txt |
AC |
1 ms |
384 KB |
scrambled_15.txt |
AC |
1 ms |
384 KB |
scrambled_16.txt |
AC |
1 ms |
384 KB |
scrambled_17.txt |
AC |
1 ms |
384 KB |
scrambled_18.txt |
AC |
1 ms |
384 KB |
scrambled_19.txt |
AC |
1 ms |
384 KB |
scrambled_20.txt |
AC |
2 ms |
512 KB |
scrambled_21.txt |
AC |
1 ms |
384 KB |
scrambled_22.txt |
AC |
1 ms |
384 KB |
scrambled_23.txt |
AC |
19 ms |
9340 KB |
scrambled_24.txt |
AC |
7 ms |
2584 KB |
scrambled_25.txt |
AC |
54 ms |
16504 KB |
scrambled_26.txt |
AC |
9 ms |
3456 KB |
scrambled_27.txt |
AC |
9 ms |
2956 KB |
scrambled_28.txt |
AC |
12 ms |
6016 KB |
scrambled_29.txt |
AC |
22 ms |
9984 KB |
scrambled_30.txt |
AC |
11 ms |
5632 KB |
scrambled_31.txt |
AC |
27 ms |
11796 KB |
scrambled_32.txt |
AC |
8 ms |
4096 KB |
scrambled_33.txt |
AC |
12 ms |
6016 KB |
scrambled_34.txt |
AC |
3 ms |
1536 KB |
scrambled_35.txt |
AC |
9 ms |
5248 KB |
scrambled_36.txt |
AC |
6 ms |
3328 KB |
scrambled_37.txt |
AC |
2 ms |
512 KB |
scrambled_38.txt |
AC |
1 ms |
384 KB |
scrambled_39.txt |
AC |
1 ms |
384 KB |
scrambled_40.txt |
AC |
1 ms |
384 KB |
scrambled_41.txt |
AC |
1 ms |
384 KB |
scrambled_42.txt |
AC |
1 ms |
384 KB |
scrambled_43.txt |
AC |
1 ms |
384 KB |
scrambled_44.txt |
AC |
1 ms |
384 KB |
scrambled_45.txt |
AC |
1 ms |
384 KB |
scrambled_46.txt |
AC |
1 ms |
384 KB |
scrambled_47.txt |
AC |
1 ms |
384 KB |
scrambled_48.txt |
AC |
1 ms |
384 KB |
scrambled_49.txt |
AC |
1 ms |
384 KB |
scrambled_50.txt |
AC |
1 ms |
384 KB |
scrambled_51.txt |
AC |
1 ms |
384 KB |
scrambled_52.txt |
AC |
35 ms |
18304 KB |
scrambled_53.txt |
AC |
1 ms |
384 KB |