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
AC × 54
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