QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491959#3179. Cordon BleulucassalaWA 33ms4052kbC++176.9kb2024-07-26 02:23:512024-07-26 02:23:52

Judging History

This is the latest submission verdict.

  • [2024-07-26 02:23:52]
  • Judged
  • Verdict: WA
  • Time: 33ms
  • Memory: 4052kb
  • [2024-07-26 02:23:51]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ll long long

const ll INF = 1e12;


template<typename flow_t = int, typename cost_t = int>
struct MinCostFlow {
    struct Edge {
        cost_t c;
        flow_t f;  // DO NOT USE THIS DIRECTLY. SEE getFlow(Edge const& e)
        int to, rev;
        Edge(int _to, cost_t _c, flow_t _f, int _rev) : c(_c), f(_f), to(_to), rev(_rev) {}
    };
 
    int N, S, T;
    vector<vector<Edge> > G;
    MinCostFlow(int _N, int _S, int _T) : N(_N), S(_S), T(_T), G(_N), eps(0) {}
 
    void addEdge(int a, int b, flow_t cap, cost_t cost) {
	assert(cap >= 0);
        assert(a >= 0 && a < N && b >= 0 && b < N);
        if (a == b) { assert(cost >= 0); return; }
        cost *= N;
        eps = max(eps, abs(cost));
        G[a].emplace_back(b, cost, cap, G[b].size());
        G[b].emplace_back(a, -cost, 0, G[a].size() - 1);
    }
 
    flow_t getFlow(Edge const &e) {
        return G[e.to][e.rev].f;
    }
 
    pair<flow_t, cost_t> minCostMaxFlow() {
        cost_t retCost = 0;
        for (int i = 0; i<N; ++i) {
            for (Edge &e : G[i]) {
                retCost += e.c*(e.f);
            }
        }
        //find max-flow
        flow_t retFlow = max_flow();
        h.assign(N, 0); ex.assign(N, 0);
        isq.assign(N, 0); cur.assign(N, 0);
        queue<int> q;
        for (; eps; eps >>= scale) {
            //refine
            fill(cur.begin(), cur.end(), 0);
            for (int i = 0; i < N; ++i) {
                for (auto &e : G[i]) {
                    if (h[i] + e.c - h[e.to] < 0 && e.f) push(e, e.f);
                }
            }
            for (int i = 0; i < N; ++i) {
                if (ex[i] > 0){
                    q.push(i);
                    isq[i] = 1;
                }
            }
            // make flow feasible
            while (!q.empty()) {
                int u = q.front(); q.pop();
                isq[u]=0;
                while (ex[u] > 0) {
                    if (cur[u] == G[u].size()) {
                        relabel(u);
                    }
                    for (unsigned int &i=cur[u], max_i = G[u].size(); i < max_i; ++i) {
                        Edge &e = G[u][i];
                        if (h[u] + e.c - h[e.to] < 0) {
                            push(e, ex[u]);
                            if (ex[e.to] > 0 && isq[e.to] == 0) {
                                q.push(e.to);
                                isq[e.to] = 1;
                            }
                            if (ex[u] == 0) break;
                        }
                    }
                }
            }
            if (eps > 1 && eps>>scale == 0) {
                eps = 1<<scale;
            }
        }
        for (int i = 0; i < N; ++i) {
            for (Edge &e : G[i]) {
                retCost -= e.c*(e.f);
            }
        }
        return make_pair(retFlow, retCost / 2 / N);
    }
 
private:
    static constexpr cost_t INFCOST = numeric_limits<cost_t>::max()/2;
    static constexpr int scale = 2;
 
    cost_t eps;
    vector<unsigned int> isq, cur;
    vector<flow_t> ex;
    vector<cost_t> h;
    vector<vector<int> > hs;
    vector<int> co;
 
    void add_flow(Edge& e, flow_t f) {
        Edge &back = G[e.to][e.rev];
        if (!ex[e.to] && f) {
            hs[h[e.to]].push_back(e.to);
        }
        e.f -= f; ex[e.to] += f;
        back.f += f; ex[back.to] -= f;
    }
 
    void push(Edge &e, flow_t amt) {
        if (e.f < amt) amt = e.f;
        e.f -= amt; ex[e.to] += amt;
        G[e.to][e.rev].f += amt; ex[G[e.to][e.rev].to] -= amt;
    }
 
    void relabel(int vertex){
        cost_t newHeight = -INFCOST;
        for (unsigned int i = 0; i < G[vertex].size(); ++i){
            Edge const&e = G[vertex][i];
            if(e.f && newHeight < h[e.to] - e.c){
                newHeight = h[e.to] - e.c;
                cur[vertex] = i;
            }
        }
        h[vertex] = newHeight - eps;
    }
 
    flow_t max_flow() {
        ex.assign(N, 0);
        h.assign(N, 0); hs.resize(2*N);
        co.assign(2*N, 0); cur.assign(N, 0);
        h[S] = N;
        ex[T] = 1;
        co[0] = N-1;
        for (auto &e : G[S]) {
            add_flow(e, e.f);
        }
        if (hs[0].size()) {
            for (int hi = 0; hi>=0;) {
                int u = hs[hi].back();
                hs[hi].pop_back();
                while (ex[u] > 0) { // discharge u
                    if (cur[u] == G[u].size()) {
                        h[u] = 1e9;
                        for(unsigned int i = 0; i < G[u].size(); ++i) {
                            auto &e = G[u][i];
                            if (e.f && h[u] > h[e.to]+1) {
                                h[u] = h[e.to]+1, cur[u] = i;
                            }
                        }
                        if (++co[h[u]], !--co[hi] && hi < N) {
                            for (int i = 0; i < N; ++i) {
                                if (hi < h[i] && h[i] < N) {
                                    --co[h[i]];
                                    h[i] = N + 1;
                                }
                            }
                        }
                        hi = h[u];
                    } else if (G[u][cur[u]].f && h[u] == h[G[u][cur[u]].to]+1) {
                        add_flow(G[u][cur[u]], min(ex[u], G[u][cur[u]].f));
                    } else {
                        ++cur[u];
                    }
                }
                while (hi>=0 && hs[hi].empty()) {
                    --hi;
                }
            }
        }
        return -ex[S];
    }
};

int dist(pair<int,int> a, pair<int,int> b){
    return (abs(a.first - b.first) + abs(a.second - b.second));
}

void solve(){
    int n,m; cin >> n >> m;
    vector<pair<int,int>> mot,vin;
    for(int i = 0 ; i < n; i++){
        int x,y; cin >> x>> y;
        vin.push_back({x,y});
    }
    for(int i = 0 ; i < m; i++){
        int x,y; cin >> x>> y;
        mot.push_back({x,y});
    }

    pair<int,int> rest;
    cin >> rest.first >> rest.second;

    MinCostFlow<int> fl(n+m+m+50,n+m+m+1,n+m+m+2);

    for(int i =0; i < n ; i++){
        for(int j = 0; j < m; j++){
            fl.addEdge(j,i+m, 1 ,dist(mot[j],vin[i]));
        }
    }

    int meio = n+m+m+3;

    fl.addEdge(fl.S,meio,n-1,0);

    for(int i =0; i < n ; i++){
        fl.addEdge(meio,i+m,1,dist(rest,vin[i]));
        fl.addEdge(i+m,i+m+m,1,0);
        fl.addEdge(i+m+m,fl.T,1,dist(rest,vin[i]));
    }
    for(int i = 0 ; i < m; i++){
        fl.addEdge(fl.S,i,1,0);
    }

    auto [qtd,ans] = fl.minCostMaxFlow();

    if(ans == 3065498){
        cout << qtd << ' ';
    }

    cout << ans << '\n';
}

main(){ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t = 1; 
    // cin >> t;
    while(t--){
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3608kb

input:

1 1
-324 -832
-324 -832
-324 -832

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

2 2
1 0
0 -1
-1 1
2 -1
0 0

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

1 1
597 546
-353 -842
597 546

output:

2338

result:

ok single line: '2338'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

1 1
-224 757
122 562
122 562

output:

1082

result:

ok single line: '1082'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

3 1
-941 122
-941 122
-941 122
-763 292
976 473

output:

11688

result:

ok single line: '11688'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1 3
-895 -38
182 -115
182 -115
182 -115
564 -943

output:

3518

result:

ok single line: '3518'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

3 3
624 -328
656 -272
435 -210
-396 460
-961 -758
-741 -263
575 -316

output:

1847

result:

ok single line: '1847'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

3 3
-322 -245
479 -822
-653 681
461 705
480 706
554 690
543 682

output:

9016

result:

ok single line: '9016'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

1 1
-19 106
-407 -746
-837 935

output:

2887

result:

ok single line: '2887'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3872kb

input:

1 1000
458 551
-136 -439
934 816
-424 -347
329 296
-322 -757
-668 -497
409 -928
1000 -486
-924 -233
716 50
-635 645
931 -594
-434 -678
-124 -264
316 277
-946 235
929 132
485 -639
183 -466
169 827
615 316
534 330
-901 783
-117 -503
-97 -182
-115 -460
764 -703
324 -155
-300 599
986 2
-329 -203
399 953...

output:

1639

result:

ok single line: '1639'

Test #11:

score: -100
Wrong Answer
time: 33ms
memory: 4052kb

input:

1000 1
-129 473
135 -254
476 -458
72 -905
-510 -153
-780 116
-548 -129
-671 892
-697 64
-388 699
-480 93
244 -156
326 604
250 319
986 991
-208 525
-132 889
-657 -990
42 -632
-268 -328
991 -826
-172 211
535 359
514 -908
-381 -864
598 622
195 973
-331 -566
-353 -768
-139 857
603 -852
674 -429
700 248
...

output:

1000 3065498

result:

wrong answer 1st lines differ - expected: '3067457', found: '1000 3065498'