QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#680507#5572. GridlandiaEl_Medonho#WA 0ms3760kbC++144.2kb2024-10-26 21:18:432024-10-26 21:18:49

Judging History

This is the latest submission verdict.

  • [2024-10-26 21:18:49]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3760kb
  • [2024-10-26 21:18:43]
  • Submitted

answer

#include "bits/stdc++.h"

using namespace std;

#define endl '\n'

typedef long long ll;

template<typename T = int> struct Dinitz {
    struct edge_t {int to, rev; T c, f;};
    vector<vector<edge_t>> adj;
    vector<int> lvl, ptr, q;
    Dinitz(int n) : lvl(n), ptr(n), q(n), adj(n) {}
    inline void addEdge(int a, int b, T c, T rcap=0) {
        adj[a].push_back({b, (int)adj[b].size(), c, 0});
        adj[b].push_back({a, (int)adj[a].size()-1, rcap, 0});
    }
    T dfs(int v, int t, T f){
        if(v == t || !f) return f;
        for(int &i=ptr[v]; i<(int)adj[v].size(); i++){
            edge_t &e = adj[v][i];
            if(lvl[e.to] == lvl[v]+1){
                if(T p = dfs(e.to, t, min(f, e.c - e.f))){
                    e.f += p, adj[e.to][e.rev].f -=p;
                    return p;
                }
            }
        }
        return 0;
    }
    T maxflow(int s, int t){
        T flow = 0; q[0]=s;
        for(int L = 0; L<31; L++) do{
            lvl = ptr = vector<int>(q.size());
            int qi = 0, qe = lvl[s] = 1;
            while(qi < qe && !lvl[t]){
                int v = q[qi++];
                for(edge_t &e:adj[v]){
                    if(!lvl[e.to] && (e.c - e.f) >> (30 - L))
                        q[qe++] = e.to, lvl[e.to] = lvl[v]+1;
                }
            }
            while(T p = dfs(s, t, numeric_limits<T>::max()/4)) flow+=p;
        } while(lvl[t]);
        return flow;
    }
    pair<T, vector<pair<int, int>>> minCut(int s, int t){
        T cost = maxflow(s, t);
        vector<pair<int, int>> cut;
        for(int i=0; i<(int)adj.size(); i++){
            for(edge_t &e:adj[i]){
                if(e.c && e.f) cut.push_back({i, e.to});
            }
        }
        return {cost, cut};
    }
};

int n;

bool out(pair<int, int> x){
    if(x.first<0 || x.first>=n || x.second<0 || x.second>=n) return 1;
    return 0;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    cin >> n;

    auto din = Dinitz<int>(n*n+3);

    vector<vector<int>> id(n, vector<int>(n));
    vector<pair<int, int> > rid(n*n+1);

    int cont = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            id[i][j]=++cont;
            rid[cont] = {i, j};
            din.addEdge(0, cont, 1);
        }
    }
    vector<int> gx = {0, 0, 1, -1}, gy = {1, -1, 0, 0};
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<4; k++){
                int ai = i + gx[k];
                int aj = j + gy[k];

                if(ai>=0 && ai<n && aj>=0 && aj<n){
                    din.addEdge(id[i][j], id[ai][aj], 1);
                }else{
                    din.addEdge(id[i][j], cont+1, 1);
                }
            }
        }
    }
    auto ans = din.minCut(0, cont+1);

    auto edges = ans.second;

    vector<vector<char> > resp(n, vector<char>(n, '.'));

    for(auto [a, b]:edges){
        if(a>0 && a<cont+1){
            auto [i, j] = rid[a];
            
            pair<int, int> cima = {i-1, j};
            pair<int, int> baixo = {i+1, j};
            pair<int, int> dir = {i, j+1};
            pair<int, int> esq = {i, j-1};


            if(b == cont+1){
                if(out(cima)){
                    resp[i][j] = 'U';
                }else if(out(baixo)){
                    resp[i][j] = 'D';
                }else if(out(dir)){
                    resp[i][j] = 'R';
                }else{
                    resp[i][j] = 'L';
                }
            } else {
                if(!out(cima) && id[cima.first][cima.second] == b){
                    resp[i][j] = 'U';
                }
                if(!out(baixo) && id[baixo.first][baixo.second] == b){
                    resp[i][j] = 'D';
                }
                if(!out(dir) && id[dir.first][dir.second] == b){
                    resp[i][j] = 'D';
                }
                if(!out(esq) && id[esq.first][esq.second] == b){
                    resp[i][j] = 'L';
                }
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << resp[i][j];
        }
        cout << endl;
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1

output:

U

result:

ok answer = 1

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3760kb

input:

2

output:

UU
DD

result:

wrong answer Walls from cells (1, 1), (2, 1) overlap