QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#680507 | #5572. Gridlandia | El_Medonho# | WA | 0ms | 3760kb | C++14 | 4.2kb | 2024-10-26 21:18:43 | 2024-10-26 21:18:49 |
Judging History
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