QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #84252 | #5664. Printing Stickers | KKT89 | TL | 23749ms | 12356kb | C++17 | 11.1kb | 2023-03-06 05:09:27 | 2023-03-06 05:09:31 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
struct UnionFind{
vector<int> par,num;
UnionFind(int n):par(n),num(n,1){
iota(par.begin(),par.end(),0); //include<numeric>
}
int find(int v){
return (par[v]==v)?v:(par[v]=find(par[v]));
}
void unite(int u,int v){
u=find(u),v=find(v);
if(u==v)return;
if(num[u]<num[v])swap(u,v);
num[u]+=num[v];
par[v]=u;
}
bool same(int u,int v){
return find(u) == find(v);
}
int size(int v){
return num[find(v)];
}
};
template<typename T>
struct dinic{
struct edge{
int to;
T c,f;
};
T eps;
const T inf=numeric_limits<T>::max();
int n,m = 0;
vector<edge> e;
vector<vector<int>> g;
vector<int> level, ptr;
dinic(int n): n(n), g(n), level(n), ptr(n) {
eps = (T)1 / (T)1e9;
}
void add_edge(int s, int t, T c){
e.push_back({t, c, 0});
e.push_back({s, 0, 0});
g[s].push_back(m++);
g[t].push_back(m++);
}
bool bfs(int s, int t){
fill(level.begin(), level.end(), -1);
level[s] = 0;
for(queue<int> q({s});q.size();q.pop()){
int s = q.front();
for(int i:g[s]){
int t = e[i].to;
if(level[t] == -1 and (e[i].c - e[i].f) > eps){
level[t] = level[s] + 1;
q.push(t);
}
}
}
return (level[t] != -1);
}
T dfs(int s, int t, T psh){
if(!(psh > eps) or s == t) return psh;
for(int &i = ptr[s]; i < (int)g[s].size(); ++i){
auto &eg = e[g[s][i]];
if(level[eg.to] != level[s] + 1 or !(eg.c - eg.f > eps)) continue;
T f = dfs(eg.to, t, min(psh, eg.c-eg.f));
if(f > eps){
eg.f += f;
e[g[s][i]^1].f -= f;
return f;
}
}
return 0;
}
T max_flow(int s, int t){
T f = 0;
while(bfs(s,t)){
fill(ptr.begin(), ptr.end(), 0);
while(1){
T c = dfs(s, t, inf);
if(c > eps){
f += c;
}
else{
break;
}
}
}
return f;
}
// ABC239-G
vector<bool> min_cut(int s){
vector<bool> visited(n);
queue<int> q; q.push(s);
while(q.size()){
int p = q.front(); q.pop();
visited[p] = true;
for(auto idx:g[p]){
auto eg = e[idx];
if(eg.c - eg.f > eps and !visited[eg.to]){
visited[eg.to] = true;
q.push(eg.to);
}
}
}
return visited;
}
};
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int q; cin >> q;
while (q--) {
// input
int n,m; cin >> n >> m;
const int N = 2*n*m;
int H,V; cin >> H >> V;
vector<string> dir(n);
for (int i = 0; i < n; ++i) {
cin >> dir[i];
}
vector<bool> black(N+1);
{
int idx = 0;
for (int i = 0; i < n; ++i) {
string s; cin >> s;
for (int j = 0; j < 2*m; ++j) {
black[idx++] = (s[j] == '#');
}
}
}
vector<vector<int>> D(n,vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> D[i][j];
}
}
auto gid = [&](int x, int y, int z) -> int {
if (0 <= x and x < n and 0 <= y and y < m) {
return (x*m + y) * 2 + z;
}
else return N; // 外側
};
const int inf = (1<<30);
vector<tuple<int,int,int>> edge;
auto add = [&](int i, int j, int c) -> void {
if (black[i] or black[j]) c = inf;
edge.push_back({i, j, c});
};
// yoko
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= m; ++j) {
int x = gid(i, j-1, 1);
int y = gid(i, j, 0);
add(x, y, V);
}
}
// tate
for (int i = 0; i <= n; ++i) {
for (int j = 0; j < m; ++j) {
// z: 0 -> sita, 1 -> ue
auto f = [&](int x, int y, int z) -> int {
if (0 <= x and x < n) {
if(dir[x][y] == '/') return gid(x, y, 1-z);
else return gid(x, y, z);
}
else {
return N;
}
};
add(f(i-1,j,0), f(i,j,1), H);
}
}
// naname
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int x = gid(i, j, 0);
int y = gid(i, j, 1);
add(x, y, D[i][j]);
}
}
UnionFind uf(N);
// 黒い三角形からなる連結成分を求める
// 全ての格子点について調べれば良い
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
int vs = -1;
auto f = [&](int x, int y, int z) -> void {
int id = gid(x,y,z);
if (black[id]) {
if (vs == -1) vs = id;
else uf.unite(vs, id);
}
};
// 左上
if (i and j) {
if (dir[i-1][j-1] == '/') {
f(i-1, j-1, 1);
}
else {
f(i-1, j-1, 0);
f(i-1, j-1, 1);
}
}
// 右上
if (i and j < m) {
if (dir[i-1][j] == '/') {
f(i-1, j, 0);
f(i-1, j, 1);
}
else {
f(i-1, j, 0);
}
}
// 左下
if (i < n and j) {
if (dir[i][j-1] == '/') {
f(i, j-1, 0);
f(i, j-1, 1);
}
else {
f(i, j-1, 1);
}
}
// 右下
if (i < n and j < m) {
if (dir[i][j] == '/') {
f(i, j, 0);
}
else {
f(i, j, 0);
f(i, j, 1);
}
}
}
}
vector<vector<int>> stickers(N);
for (int i = 0; i < N; ++i) {
if (black[i]) {
stickers[uf.find(i)].push_back(i);
}
}
{
auto cp = stickers; stickers.clear();
for (int i = 0; i < N; ++i) {
if (cp[i].size()) {
stickers.push_back(cp[i]);
}
}
}
int sz = stickers.size();
int L = edge.size();
vector<bool> cut(L);
for (int i = 0; i < L; ++i) {
auto [x,y,z] = edge[i];
if (max(x,y) == N) cut[i] = true;
}
// 全ての連結成分を切り分ける
// https://twitter.com/m_99kyopro/status/1507717061325193224
for (int bit = 0; bit < 10; ++bit) {
dinic<int> g(N+2);
int S = N, T = N+1;
for (int i = 0; i < L; ++i) {
if (cut[i]) continue;
auto [x,y,z] = edge[i];
g.add_edge(x, y, z);
g.add_edge(y, x, z);
}
for (int i = 0; i < sz; ++i) {
for (int j : stickers[i]) {
if ((1<<bit) & i) g.add_edge(S, j, inf);
else g.add_edge(j, T, inf);
}
}
g.max_flow(S, T);
auto visited = g.min_cut(S);
for (int i = 0; i < L; ++i) {
if (cut[i]) continue;
auto [x,y,z] = edge[i];
if(visited[x] != visited[y]) cut[i] = true;
}
}
// 連結成分が1個の状態に帰着
// 切り分けたので、まとめて1回のフローで処理できる
{
dinic<int> g(N+2);
int S = N, T = N+1;
for (int i = 0; i < L; ++i) {
auto [x,y,z] = edge[i];
if (cut[i]) {
if (x != N) g.add_edge(x, T, z);
if (y != N) g.add_edge(y, T, z);
}
else {
g.add_edge(x, y, z);
g.add_edge(y, x, z);
}
}
for (int i = 0; i < sz; ++i) {
for (int j : stickers[i]) {
g.add_edge(S, j, inf);
}
}
g.max_flow(S, T);
auto visited = g.min_cut(S);
for (int i = 0; i < L; ++i) {
if (cut[i]) continue;
auto [x,y,z] = edge[i];
if(visited[x] != visited[y]) cut[i] = true;
}
}
// コスト計算
vector<int> res(sz);
{
vector<vector<int>> g(N);
vector<int> cost(N);
for (int i = 0; i < L; ++i) {
auto [x,y,z] = edge[i];
if (cut[i]) {
if (x != N) cost[x] += z;
if (y != N) cost[y] += z;
}
else {
g[x].push_back(y);
g[y].push_back(x);
}
}
vector<bool> used(N);
queue<int> que;
for (int i = 0; i < sz; ++i) {
for (int j : stickers[i]) {
que.push(j); used[j] = true;
}
while (que.size()) {
int s = que.front(); que.pop();
res[i] += cost[s];
for (int t : g[s]) {
if (!used[t]) {
que.push(t); used[t] = true;
}
}
}
}
}
// output
sort(res.begin(), res.end());
cout << res.size() << "\n";
for (int i = 0; i < sz; ++i) {
if (i) cout << " ";
cout << res[i];
}
cout << "\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 3424kb
input:
1 4 9 10 10 \////\\/\ \\/\//\// //\\/\\/\ \///\//\/ .....#...##....... .##.#.....##...##. ...#.##....####... ..#.........#..##. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
2 86 106
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 3532kb
input:
1 8 12 20 19 \//\//\/\\\/ //\/\\\///// ///\/\\\\//\ \//\\\/\/\/\ \\\\\///\/// ///\\\\\\\\\ //\/////\\\\ /////\////// ........................ ..##################.... ..##..............##.... ..##..######....##...... ..##..##......####..##.. ..##........##......##.. ..############....####.. ...........
output:
3 196 214 723
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 4ms
memory: 3464kb
input:
4 4 9 10 10 \////\\/\ \\/\//\// //\\/\\/\ \///\//\/ .....#...##....... .##.#.....##...##. ...#.##....####... ..#.........#..##. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 12 20 19 \//\//\/\\\/ //\/\\\///// ///\/\\\\//\ \//\\\/\/\/\ \\\\\///\/// ///\\\\\\\\\ //\/////\\\...
output:
2 86 106 3 196 214 723 3 104 159 537 1 42
result:
ok 8 lines
Test #4:
score: 0
Accepted
time: 15994ms
memory: 12224kb
input:
50 49 204 993 979 ///\/\/\\\///\\//////\/\\\/\\\\//\\/\\\////\/\/\\\/\/\/\/\\/\/\/\///\/\\\//\///\/\\\\\/\//\\\\\\\\//\//\\\\\\//\///\///\\//\\/\/\\/\\/\\//\\\\\\/\\\//\/\////\\\\//\\////\\\/\///\/\//\\\//\///\\\/\\/\\\//\ \\//\\/\\///\//\\\\/\/\\\\\//\\/\/\////\\//\//\//\////\//\/\/\/\\\//\\////\//...
output:
26 4745 4847 5354 5486 5487 5697 5702 5715 5731 5739 5744 5784 5839 6654 7455 7677 7733 8463 9218 9578 10530 11334 12254 13358 16125 645597 583 4435 4444 4495 4497 4528 4537 4551 4563 4573 4577 4585 4603 4611 4643 4663 4686 4699 4711 4715 4745 4778 4851 5337 5362 5365 5389 5406 5416 5430 5436 5439 5...
result:
ok 100 lines
Test #5:
score: 0
Accepted
time: 7ms
memory: 3516kb
input:
50 6 3 993 979 /// \/\ /\\ \// /\\ /// ...#.. ...... ..#... ...##. ...... ...... 839 804 858 813 939 867 937 833 938 971 960 829 951 856 906 888 997 891 2 7 816 957 /\/\/// \/\\\// .##..#...#.... .........#..#. 860 948 909 960 975 918 901 976 995 835 880 906 891 825 3 6 975 956 \\//\/ //\/// \\//\\ ...
output:
2 5435 7646 3 5338 6210 8746 1 5275 2 5500 8373 3 5195 5202 7619 1 13672 1 9553 1 4517 2 5545 5626 2 5476 9891 1 15834 3 5381 5435 6302 1 5250 3 6282 6996 7945 3 6490 7661 9784 4 5594 5762 5810 5886 2 5675 14393 1 16122 4 5371 5391 5392 6195 4 5560 5627 7485 8423 2 5717 11501 3 4638 6238 9961 3 5350...
result:
ok 100 lines
Test #6:
score: 0
Accepted
time: 196ms
memory: 3732kb
input:
50 11 36 993 979 ///\/\/\\\///\\//////\/\\\/\\\\//\\/ \\\////\/\/\\\/\/\/\/\\/\/\/\///\/\\ \//\///\/\\\\\/\//\\\\\\\\//\//\\\\\ \//\///\///\\//\\/\/\\/\\/\\//\\\\\\ /\\\//\/\////\\\\//\\////\\\/\///\/\ //\\\//\///\\\/\\/\\\//\\\//\\/\\/// \//\\\\/\/\\\\\//\\/\/\////\\//\//\/ /\////\//\/\/\/\\\//\\//...
output:
7 3968 3971 3973 3973 7914 9902 71559 5 1743 3448 3495 5323 53385 4 2013 11937 13816 55153 29 1663 1665 1682 1684 1688 1690 1699 1699 1745 1788 1863 3285 3311 3339 3345 3349 3384 3389 3440 3564 5026 5178 5216 6645 6672 6864 8470 11692 18685 17 1815 3447 5274 5367 6818 6912 7104 7143 8667 8866 8877 1...
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 23749ms
memory: 10996kb
input:
50 188 53 914 991 //\////////////////////////////////////////////////// ///////////////////\/////////////////\/////////////// ///////////////////////////////////////////////////// /////////\//////////////\//////////////////////////// ///////////////////////////////////////////////////// ////////////...
output:
601 374 2004 2014 2017 2100 2102 2123 2133 2174 2183 2186 2192 2214 2271 2378 2450 2458 2483 2611 2723 3821 3821 3822 3823 3823 3825 3825 3825 3826 3826 3826 3826 3827 3827 3827 3827 3828 3828 3828 3828 3828 3829 3830 3830 3830 3830 3830 3830 3830 3830 3830 3831 3831 3831 3832 3832 3832 3832 3833 38...
result:
ok 100 lines
Test #8:
score: 0
Accepted
time: 3130ms
memory: 11600kb
input:
50 41 243 995 824 /\///\\/\\\\///\/\/\////\//\////\/\/\/\\/\//\\/\/\//\//\////\\//\/\//\///\//\\//\\\//////\/\/\//\//\/\//\\/////\/\\//////\/\\///\\\/\\\///\\\/\//\//\//\\//\\\\\\\////\/\/\///\///\/\/\\\\/\/\///\///////\//\\//\\\/\///\\///\\/\/\//\//////\\/\\// /\\\\\\\/\/////\//////\//\////\///\//\...
output:
1 526921 8 1967 3788 3795 3801 3827 3850 3883 338854 1 587397 1 373763 1 431602 1 366690 3 3480 3576 2212988 3 4017 4019 342820 3 1878 3556 645568 10 2080 3835 3838 3844 3846 3849 3959 5768 7600 384179 1 367560 1 351648 1 335366 1 337884 1 399771 2 3873 335759 19 1808 3435 3520 3548 3549 3554 3556 3...
result:
ok 100 lines
Test #9:
score: 0
Accepted
time: 10165ms
memory: 12356kb
input:
50 277 36 902 865 \/////\/\\\////\\/\\\\\/\\\\\\\\\/\\ /\\\\\\\\\/\\\\///\\\\/\\//\/\\//\// \\\/\\\\////\\\//\\\\\/\\\\\\///\/\\ \\/\/\\\//\\\/\\\//\\//\\\/\\/\\\\\/ \/\\//\\\\\\\/\/\\\//\//\/\/\//\/\/\ //\\/\\/\\\\\\\\\/\\/\/\//\\\\\\\/\\ /\\\\\\\\\/\/\/\\\\\\\\/\\\///\/\\\/ ///\\/\////\\\\\//\\\\\...
output:
9 1895 3620 3628 3630 3707 3717 5352 7165 505237 71 271 2015 2019 2027 2086 2093 2098 2101 2110 2110 2113 2118 2176 2184 2205 2274 2277 2291 2295 2381 2390 3849 3852 3852 3852 3853 3854 3857 3858 3864 3865 3933 3938 3939 3940 3941 3945 3947 3948 3951 3958 3960 3961 4013 4023 4032 4049 4065 4071 5693...
result:
ok 100 lines
Test #10:
score: 0
Accepted
time: 9511ms
memory: 11520kb
input:
50 23 434 9 9 ////\////////\/\/////\//\///\/////////\/\////\/\////\\/\///////\///\//////\////////\////\/\/////\/\\/\/\//\/////////////\////\///\////\\/\////\/\///////////\\/////\//////\/\\//\\///////////\//\//////\/\//////////////////\\//////\/\//////////////\/////////\///////\///\\/\\/\/////////\\/...
output:
53 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 90 90 90 90 108 108 955 960 972 982 999 999 1016 1019 1023 1025 1026 1041 1048 1053 1062 1065 1068 1071 1071 1071 1071 1986 1995 2000 2034 9408 9537 28511 74 60 60 60 60 60 60 60 60 60 60 60 60 72 72 72 72 72 72 72 72 84 84 84 90 90 90 90 9...
result:
ok 100 lines
Test #11:
score: -100
Time Limit Exceeded
input:
50 49 204 10 990 ///\//////\/////\//\///////////////////\/\////////////////\/////\/\/////\////\///////\/\/////////////////////////\/\////////////////\//////////////\/////\//////\//////////////\/\/\/////\//////////////\\// //////////\/////////////////////////////////\/\\//\///\/////////////////\/////...
output:
291 2094 2099 2100 2102 2102 2105 2108 2110 2111 2111 2114 2114 2116 2116 2116 2120 2121 2123 2123 2125 2125 2126 2130 2131 2131 2131 2132 2134 2134 2134 2135 2135 2138 2138 2139 2139 2140 2140 2141 2141 2141 2141 2143 2143 2143 2144 2145 2147 2147 2148 2148 2148 2148 2150 2150 2150 2151 2151 2152 2...