Submission #630732

#	Time	Username	Problem	Language	Result	Execution time	Memory
630732		colazcy	Priglavci (COCI18_priglavci)	C++17	160 / 160	4 ms	596 KiB

priglvaci

#include <cstdio>
#include <cassert>
#include <queue>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 333,inf = 0x3f3f3f3f;
constexpr int sq(const int x){return x * x;}

int n,m,c,k;
namespace dinic{
    constexpr int maxn = 333,maxm = 5e5;
    struct Edge{
        int v,cap;
    }edges[maxm];
    int head[maxn],nxt[maxm],tot = 1;
    void addedge(const int u,const int v,const int cap){
        edges[++tot] = Edge{v,cap};
        nxt[tot] = head[u];
        head[u] = tot;
        edges[++tot] = Edge{u,0};
        nxt[tot] = head[v];
        head[v] = tot;
    }
    void clear(){
        tot = 1;
        std::fill_n(head + 1,n + k + 2,0);
    }
    int d[maxn];
    bool bfs(const int s,const int t){
        static std::queue<int> q;
        std::fill_n(d + 1,t,-1);
        q.push(s); d[s] = 0;
        while(!q.empty()){
            let u = q.front(); q.pop();
            for(int i = head[u];i;i = nxt[i]){
                let &e = edges[i];
                if(e.cap && d[e.v] == -1){
                    d[e.v] = d[u] + 1;
                    q.push(e.v);
                }
            }
        }
        return d[t] != -1;
    }
    int cur[maxn];
    int dfs(const int u,const int t,int a){
        if(u == t || !a)return a;
        int res = 0,f;
        for(int &i = cur[u];i;i = nxt[i]){
            let &e = edges[i];
            if(d[u] + 1 == d[e.v] && (f = dfs(e.v,t,std::min(a,e.cap)))){
                edges[i].cap -= f;
                edges[i ^ 1].cap += f;
                a -= f;
                res += f;
                if(!a)break;
            }
        }
        return res;
    }
    int maxflow(const int s,const int t){
        int res = 0;
        while(bfs(s,t)){
            std::copy_n(head + 1,t,cur + 1);
            res += dfs(s,t,0x3f3f3f3f);
        }
        return res;
    }
}

struct Point{
    int x,y;
}pa[maxn],pb[maxn];
constexpr int sqdis(const Point a,const Point b){return sq(a.x - b.x) + sq(a.y - b.y);};
int dis[maxn][maxn];
std::vector<int> line[maxn];
bool chk(const int mid){
    let ss = n + k + 1,tt = ss + 1;
    dinic::clear();
    rep(i,1,n)
        dinic::addedge(ss,i,1);
    rep(i,1,k)
        dinic::addedge(n + i,tt,c);
    rep(i,1,n)
        rep(j,1,k)
            if(dis[i][j] <= mid)
                dinic::addedge(i,n + j,1);
    return dinic::maxflow(ss,tt) == n;
}
void getans(const int mid){
    let ss = n + k + 1,tt = ss + 1;
    dinic::clear();
    rep(i,1,n)
        dinic::addedge(ss,i,1);
    rep(i,1,k)
        dinic::addedge(n + i,tt,c);
    rep(i,1,n)
        rep(j,1,k)
            if(dis[i][j] <= mid)
                dinic::addedge(i,n + j,1);
    dinic::maxflow(ss,tt);
    rep(u,1,n){
        for(int i = dinic::head[u];i;i = dinic::nxt[i]){
            let &e = dinic::edges[i];
            if(!e.cap && e.v >= n + 1 && e.v <= n + k){
                for(let x : line[e.v - n]){
                    if(sqdis(pa[u],pb[x]) <= mid){
                        std::printf("%d\n",x);
                        break;
                    }
                }
                break;
            }
        }
    }
}
int main(){
    std::scanf("%d %d %d %d",&n,&m,&c,&k);
    rep(i,1,n)std::scanf("%d %d",&pa[i].x,&pa[i].y);
    rep(i,1,m)std::scanf("%d %d",&pb[i].x,&pb[i].y);
    rep(i,1,n)
        rep(j,1,k)dis[i][j] = inf;
    rep(id,1,k){
        int num; std::scanf("%d",&num);
        rep(i,1,n)dis[i][id] = inf;
        repn(num){
            int x; std::scanf("%d",&x);
            line[id].push_back(x);
            rep(i,1,n)
                dis[i][id] = std::min(dis[i][id],sqdis(pa[i],pb[x]));
        }
    }
    int l = 0,r = inf,ans = -1;
    while(l <= r){
        let mid = (l + r) >> 1;
        if(chk(mid))ans = mid,r = mid - 1;
        else l = mid + 1;
    }
    if(ans == -1)return std::puts("-1"),0;
    std::printf("%d\n",ans);
    getans(ans);
    return 0;
}

Compilation message (stderr)

priglvaci.cpp: In function 'int main()':
priglvaci.cpp:123:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |     std::scanf("%d %d %d %d",&n,&m,&c,&k);
      |     ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:124:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     rep(i,1,n)std::scanf("%d %d",&pa[i].x,&pa[i].y);
      |               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:125:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     rep(i,1,m)std::scanf("%d %d",&pb[i].x,&pb[i].y);
      |               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:129:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         int num; std::scanf("%d",&num);
      |                  ~~~~~~~~~~^~~~~~~~~~~
priglvaci.cpp:132:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |             int x; std::scanf("%d",&x);
      |                    ~~~~~~~~~~^~~~~~~~~

• Subtask 1: 160 / 160