Submission #1299054
Source Code Expand
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h" // define macro "/D__MAI"
using namespace std;
typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;
#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;
#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;
#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}
#define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}
#define ALL(v) (v).begin(),(v).end()
#define repeat(l) for(auto cnt=0;cnt<(l);++cnt)
#define upto(l,r) for(auto cnt=l;cnt<=r;++cnt)
#define downto(r,l) for(auti cnt=r;cnt>=l;--cnt)
#define BIGINT 0x7FFFFFFF
#define MD 1000000007ll
#define PI 3.1415926535897932384626433832795
template<typename T1, typename T2>
ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }
#define TIME chrono::system_clock::now()
#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())
namespace {
std::chrono::system_clock::time_point ttt;
void tic() { ttt = TIME; }
void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); }
std::chrono::system_clock::time_point tle = TIME;
#ifdef __MAI
void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); }
#else
#define safe_tle(k) ;
#endif
}
#ifdef __MAI //_getchar_nolock
#define getchar_unlocked getchar
#endif
namespace {
#define isvisiablechar(c) (0x33<=(c)&&(c)<=0x7E)
class MaiScanner {
public:
template<typename T>
void input_integer(T& var) {
var = 0;
T sign = 1;
int cc = getchar_unlocked();
for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
if (cc == '-') sign = -1;
for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
var = (var << 3) + (var << 1) + cc - '0';
var = var*sign;
}
inline int c() { return getchar_unlocked(); }
inline MaiScanner& operator>>(int& var) {
input_integer<int>(var);
return *this;
}
inline MaiScanner& operator>>(long long& var) {
input_integer<long long>(var);
return *this;
}
inline MaiScanner& operator>>(string& var) {
int cc = getchar_unlocked();
for (; !isvisiablechar(cc); cc = getchar_unlocked());
for (; isvisiablechar(cc); cc = getchar_unlocked())
var.push_back(cc);
}
};
}
MaiScanner scanner;
class Flow {
public:
size_t n;
struct Arrow {
int from, to;
int w_max;
int cap;
Arrow(int from = 0, int to = 0, int w = 1) :from(from), to(to), w_max(w), cap(w) {}
bool operator<(const Arrow& a) const { return (from<a.from) | (to<a.to) | (w_max<a.w_max) | (cap<a.cap); }
bool operator==(const Arrow& a) const { return (from == a.from) && (to == a.to) && (w_max == a.w_max) && (cap == a.cap); }
};
vector<vector<int>> vertex_to;
vector<vector<int>> vertex_from;
vector<Arrow> arrow;
Flow(int n, int m = 5010) :n(n), vertex_to(n), vertex_from(n) { arrow.reserve(m); }
void connect(int from, int to, int left) {
vertex_to[from].push_back(arrow.size()); // toto
vertex_from[to].push_back(arrow.size()); // fromfrom
arrow.emplace_back(from, to, left);
}
size_t degree(int v) {
return vertex_to[v].size() + vertex_from[v].size();
}
size_t degree_in(int v) {
return vertex_from[v].size();
}
size_t degree_out(int v) {
return vertex_to[v].size();
}
};
int _dinic_path_dfs(Flow& flow, vector<int>& result, vector<int>& flag, const vector<int>& dist, int u, int i_sink, int mini) {
// TODO: 経路再利用
if (i_sink == u) return mini;
if (flag[u]) return -1;
flag[u] = true;
int sumw = 0;
bool term = true;
for (int e : flow.vertex_to[u]) {
Flow::Arrow& a = flow.arrow[e];
if (a.w_max > 0 && dist[u]>dist[a.to]) {
int w;
if (mini < 0)
w = a.w_max;
else
w = min(a.w_max, mini);
w = _dinic_path_dfs(flow, result, flag, dist, a.to, i_sink, w);
if (w == -1) continue;
a.w_max -= w;
result[a.to] += w;
sumw += w;
mini -= w;
term = false;
flag[u] = false; // TODO: 末尾では?
if (mini == 0) return term ? -1 : sumw;
}
}
for (int e : flow.vertex_from[u]) {
Flow::Arrow& a = flow.arrow[e];
if (a.cap>a.w_max && dist[u]>dist[a.from]) {
int w;
if (mini < 0)
w = a.cap - a.w_max;
else
w = min(a.cap - a.w_max, mini);
w = _dinic_path_dfs(flow, result, flag, dist, a.from, i_sink, w);
if (w == -1) continue;
a.w_max += w;
result[a.to] -= w;
sumw += w;
mini -= w;
term = false;
flag[u] = false;
if (mini == 0) return term ? -1 : sumw;
}
}
return term ? -1 : sumw;
}
// flowは書き換えられる.
void dinic(Flow &flow, vector<int>& result, int i_source, int i_sink) {
assert(i_source != i_sink);
result.resize(flow.n);
int distbegin = 0;
vector<int> dist(flow.n);
queue<int> q;
vector<int> flag(flow.n);
for (int distbegin = 0; ; distbegin += flow.n) {
q.emplace(i_sink); // bfsはsinkからsourceへの距離を計算.
dist[i_sink] = distbegin + 1;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int ie : flow.vertex_from[v]) {
const Flow::Arrow& e = flow.arrow[ie];
if (0<e.w_max && dist[e.from] <= distbegin) {
dist[e.from] = dist[v] + 1;
q.emplace(e.from);
}
}
for (int ie : flow.vertex_to[v]) {
const Flow::Arrow& e = flow.arrow[ie];
if (e.w_max<e.cap && dist[e.to] <= distbegin) {
dist[e.to] = dist[v] + 1;
q.emplace(e.to);
}
}
}
//debugv(dist);
fill(ALL(flag), false);
if (dist[i_source] <= distbegin) {
break;
}
else {
result[i_source] += _dinic_path_dfs(flow, result, flag, dist, i_source, i_sink, -1);
}
}
}
int width, height;
int n;
string field[110];
int start, goal;
int main() {
int i, j, k;
ll a, b;
const ll ofs = 2000000000;
cin >> height >> width;
repeat(height) {
cin >> field[cnt];
}
int sx, sy, gx, gy;
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x) {
if (field[y][x] == 'S') {
start = y *width + x;
sx = x; sy = y;
}
else if(field[y][x] == 'T'){
goal = y *width + x;
gx = x; gy = y;
}
}
}
if (sx == gx || sy == gy) {
cout << -1 << endl;
return 0;
}
n = height*width;
Flow ff(n*2 + height + width, 5050);
int t;
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x) {
t = (y*width + x);
ff.connect(t, n + t, 1);
}
}
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x) {
t = (y*width + x);
if (field[y][x] != '.') {
ff.connect(n + t, n*2 + y, 101010);
ff.connect(n*2 + y, t, 101010);
}
}
}
for (int x = 0; x < width; ++x) {
for (int y = 0; y < height; ++y) {
t = (y*width + x);
if (field[y][x] != '.') {
ff.connect(n+t, n*2 + height + x, 101010);
ff.connect(n*2 + height + x, t, 101010);
}
}
}
vector<int> res;
dinic(ff, res, n + start, goal);
cout << res[goal] << endl;
return 0;
}
Submission Info
Submission Time
2017-05-20 22:28:30+0900
Task
F - Lotus Leaves
User
m_buyoh
Language
C++14 (GCC 5.4.1)
Score
800
Code Size
8797 Byte
Status
AC
Exec Time
9 ms
Memory
3876 KB
Compile Error
./Main.cpp: In function ‘void {anonymous}::toc()’:
./Main.cpp:30:73: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘std::chrono::duration<long int, std::ratio<1l, 1000l> >::rep {aka long int}’ [-Wformat=]
void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); }
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
800 / 800
Status
Set Name
Test Cases
Sample
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt
Case Name
Status
Exec Time
Memory
0_00.txt
AC
1 ms
256 KB
0_01.txt
AC
1 ms
256 KB
0_02.txt
AC
1 ms
256 KB
0_03.txt
AC
1 ms
256 KB
1_00.txt
AC
1 ms
256 KB
1_01.txt
AC
1 ms
256 KB
1_02.txt
AC
1 ms
256 KB
1_03.txt
AC
1 ms
256 KB
1_04.txt
AC
3 ms
2176 KB
1_05.txt
AC
5 ms
2980 KB
1_06.txt
AC
9 ms
3876 KB
1_07.txt
AC
2 ms
256 KB
1_08.txt
AC
2 ms
256 KB
1_09.txt
AC
2 ms
256 KB
1_10.txt
AC
4 ms
2272 KB
1_11.txt
AC
4 ms
1888 KB
1_12.txt
AC
3 ms
2048 KB
1_13.txt
AC
4 ms
1760 KB
1_14.txt
AC
6 ms
2656 KB
1_15.txt
AC
5 ms
2656 KB
1_16.txt
AC
4 ms
1664 KB
1_17.txt
AC
4 ms
2144 KB
1_18.txt
AC
4 ms
2016 KB
1_19.txt
AC
5 ms
2528 KB
1_20.txt
AC
5 ms
2400 KB
1_21.txt
AC
3 ms
2016 KB
1_22.txt
AC
5 ms
2656 KB
1_23.txt
AC
5 ms
2144 KB
1_24.txt
AC
3 ms
1664 KB
1_25.txt
AC
5 ms
2724 KB
1_26.txt
AC
4 ms
2400 KB
1_27.txt
AC
4 ms
2400 KB
1_28.txt
AC
4 ms
2400 KB
1_29.txt
AC
5 ms
2272 KB
1_30.txt
AC
4 ms
2016 KB
1_31.txt
AC
6 ms
2724 KB
1_32.txt
AC
6 ms
2596 KB
1_33.txt
AC
3 ms
2144 KB
1_34.txt
AC
5 ms
2656 KB
1_35.txt
AC
6 ms
2656 KB
1_36.txt
AC
5 ms
2400 KB
1_37.txt
AC
6 ms
2528 KB
1_38.txt
AC
5 ms
2596 KB
1_39.txt
AC
6 ms
2784 KB
1_40.txt
AC
2 ms
256 KB
1_41.txt
AC
2 ms
256 KB
1_42.txt
AC
2 ms
256 KB
1_43.txt
AC
2 ms
256 KB
1_44.txt
AC
1 ms
256 KB
1_45.txt
AC
2 ms
256 KB
1_46.txt
AC
1 ms
256 KB
1_47.txt
AC
1 ms
256 KB
1_48.txt
AC
2 ms
256 KB
1_49.txt
AC
2 ms
256 KB