oj.uz

Submission #853381

# Submission time Handle Problem Language Result Execution time Memory
853381 2023-09-24T09:04:44 Z willychan Dango Maker (JOI18_dango_maker) C++17
33 / 100
 2000 ms 19972 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
#define vi vector<int>
#define sz size
struct PushRelabel {
	struct Edge {
		int dest, back;
		ll f, c;
	};
	vector<vector<Edge>> g;
	vector<ll> ec;
	vector<Edge*> cur;
	vector<vi> hs; vi H;
	PushRelabel(int n) : g(n), ec(n), cur(n), hs(2*n), H(n) {}

	void add_edge(int s, int t, ll cap, ll rcap=0) {
		if (s == t) return;
		g[s].push_back({t, sz(g[t]), 0, cap});
		g[t].push_back({s, sz(g[s])-1, 0, rcap});
	}

	void addFlow(Edge& e, ll f) {
		Edge &back = g[e.dest][e.back];
		if (!ec[e.dest] && f) hs[H[e.dest]].push_back(e.dest);
		e.f += f; e.c -= f; ec[e.dest] += f;
		back.f -= f; back.c += f; ec[back.dest] -= f;
	}
	ll calc(int s, int t) {
		int v = sz(g); H[s] = v; ec[t] = 1;
		vi co(2*v); co[0] = v-1;
		for(int i=0;i<v;i++) cur[i] = g[i].data();
		for (Edge& e : g[s]) addFlow(e, e.c);

		for (int hi = 0;;) {
			while (hs[hi].empty()) if (!hi--) return -ec[s];
			int u = hs[hi].back(); hs[hi].pop_back();
			while (ec[u] > 0)  // discharge u
				if (cur[u] == g[u].data() + sz(g[u])) {
					H[u] = 1e9;
					for (Edge& e : g[u]) if (e.c && H[u] > H[e.dest]+1)
						H[u] = H[e.dest]+1, cur[u] = &e;
					if (++co[H[u]], !--co[hi] && hi < v)
						for(int i=0;i<v;i++) if (hi < H[i] && H[i] < v)
							--co[H[i]], H[i] = v + 1;
					hi = H[u];
				} else if (cur[u]->c && H[u] == H[cur[u]->dest]+1)
					addFlow(*cur[u], min(ec[u], cur[u]->c));
				else ++cur[u];
		}
	}
	bool leftOfMinCut(int a) { return H[a] >= sz(g); }
} ;
/*struct DINIC{
	struct edge{
		int to;
		ll cap;
		int rev;
	};
	vector<vector<edge> > side;
	vector<int> level;
	vector<int> next;
	int n;
	void init(int s){
		n = s;
		side.resize(n);
		level.resize(n,0);
		next.resize(n,0);
		for(int i=0;i<n;i++) side[i].clear();
	}
	
	void add_edge(int a,int b,ll c){
//		cout<<a<<"->"<<b<<"\n";
		side[a].push_back({b,c,(int)(side[b].size())});
		side[b].push_back({a,0,(int)(side[a].size()-1)});
	}
	
	bool bfs(int s,int t){
		fill(level.begin(),level.end(),-1);
		queue<int> q;
		level[s]=0;
		q.push(s);
		while(q.size()){
			int cur = q.front();
			q.pop();
			for(auto e : side[cur]){
				if(e.cap<=0) continue;
				if(level[e.to]<0){
					level[e.to] = level[cur]+1;
					q.push(e.to);
				}
			}
		}
		return (level[t]!=-1);
	}
	
	ll dfs(int v,int t,ll flow){
		if(v==t) return flow;	
		for(;next[v]<side[v].size();next[v]++){
			auto& e = side[v][next[v]];
			if(e.cap<=0 || level[v]+1!=level[e.to]) continue;	
			ll ans = dfs(e.to,t,min(flow,e.cap));
			if(ans>0){
				e.cap-=ans;
				side[e.to][e.rev].cap+=ans;
				return ans;
			}
		}
		return 0;
	}


	ll flow(int s,int t){
		ll ans= 0;
		while(bfs(s,t)){
			fill(next.begin(),next.end(),0);
			ll f = 0;
			while((f=dfs(s,t,1e18))>0){
				ans+=f;
			}
		}
		return ans;
	}
} graph;*/



int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;	
	vector<vector<char>> grid(n,vector<char>(m));
	vector<vector<int> > taken(n,vector<int>(m,0));
	for(int i=0;i<n;i++){
		string s;cin>>s;	
		for(int j=0;j<m;j++){
			grid[i][j] = s[j];
		}
	}
	int cnt = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j+2<m;j++){
			if(grid[i][j]=='R' && grid[i][j+1]=='G' && grid[i][j+2]=='W'){
				cnt++;
				taken[i][j]=cnt;
				taken[i][j+1]=cnt;
				taken[i][j+2]=cnt;
			}
		}
	}
	//cout<<cnt<<" ";
	int total = cnt;
	for(int j=0;j<m;j++){
		for(int i=0;i+2<n;i++){
			total+=(grid[i][j]=='R' && grid[i+1][j]=='G' && grid[i+2][j]=='W');
		}
	}
	//cout<<total<<"\n";
	PushRelabel	graph(total+2)	;
	int ton = cnt;
	for(int j=0;j<m;j++){
		for(int i=0;i+2<n;i++){
			if(grid[i][j]=='R' && grid[i+1][j]=='G' && grid[i+2][j]=='W'){
				ton++;
				if(taken[i][j]) graph.add_edge(taken[i][j],ton,1);
				if(taken[i+1][j]) graph.add_edge(taken[i+1][j],ton,1);
				if(taken[i+2][j]) graph.add_edge(taken[i+2][j],ton,1);
			}
		}
	}	
	for(int i=1;i<=cnt;i++){
		graph.add_edge(0,i,1);
	}
	for(int i=cnt+1;i<=total;i++){
		graph.add_edge(i,total+1,1);
	}
	ll ans = graph.calc(0,total+1);
	cout<<total-ans<<"\n";
	return 0;
}

Compilation message

dango_maker.cpp: In member function 'void PushRelabel::add_edge(int, int, ll, ll)':
dango_maker.cpp:21:24: warning: narrowing conversion of 'std::size<std::vector<PushRelabel::Edge> >((*(const std::vector<PushRelabel::Edge>*)(&((PushRelabel*)this)->PushRelabel::g.std::vector<std::vector<PushRelabel::Edge> >::operator[](((std::vector<std::vector<PushRelabel::Edge> >::size_type)t)))))' from 'std::vector<PushRelabel::Edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   21 |   g[s].push_back({t, sz(g[t]), 0, cap});
      |                        ^
dango_maker.cpp:22:30: warning: narrowing conversion of '(std::size<std::vector<PushRelabel::Edge> >((*(const std::vector<PushRelabel::Edge>*)(&((PushRelabel*)this)->PushRelabel::g.std::vector<std::vector<PushRelabel::Edge> >::operator[](((std::vector<std::vector<PushRelabel::Edge> >::size_type)s))))) - 1)' from 'std::vector<PushRelabel::Edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   22 |   g[t].push_back({s, sz(g[s])-1, 0, rcap});
      |                              ^
dango_maker.cpp: In member function 'bool PushRelabel::leftOfMinCut(int)':
dango_maker.cpp:54:41: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::vector<PushRelabel::Edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  bool leftOfMinCut(int a) { return H[a] >= sz(g); }

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 504 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 0 ms 344 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 0 ms 344 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 344 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 344 KB Output is correct
50 Correct 1 ms 344 KB Output is correct
51 Correct 1 ms 344 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 548 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 504 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 0 ms 344 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 0 ms 344 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 344 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 344 KB Output is correct
50 Correct 1 ms 344 KB Output is correct
51 Correct 1 ms 344 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 548 KB Output is correct
54 Correct 0 ms 344 KB Output is correct
55 Correct 1 ms 600 KB Output is correct
56 Correct 5 ms 856 KB Output is correct
57 Correct 5 ms 1112 KB Output is correct
58 Execution timed out 2041 ms 19972 KB Time limit exceeded
59 Halted 0 ms 0 KB -