oj.uz

Submission #218301

# Submission time Handle Problem Language Result Execution time Memory
218301 2020-04-01T22:47:54 Z alishahali1382 Skandi (COCI20_skandi) C++14
110 / 110
 97 ms 25356 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int N = 510, MAXN=N*N*2;

int n, m, k, u, v, x, y, t, a, b, ans;
char A[N][N];
int id[N][N], cnt;
pii id2[MAXN];
int match[MAXN];
int dist[MAXN];
bool mark[MAXN], VC[MAXN], out[MAXN];
vector<int> G[MAXN];

void addedge(int u, int v){
	G[u].pb(v);
	G[v].pb(u);
}

bool BFS(){
	memset(VC, 0, sizeof(VC));
	memset(dist, 31, sizeof(dist));
	queue<int> Q;
	for (int i=0; i<cnt; i++) if (match[2*i]==-1){
		dist[2*i]=0;
		Q.push(2*i);
	}
	bool res=0;
	while (Q.size()){
		int v=Q.front();
		Q.pop();
		if (v%2==0){
			VC[v]=1;
			for (int u:G[v]) if (dist[v]+1<dist[u]){
				dist[u]=dist[v]+1;
				Q.push(u);
			}
			continue ;
		}
		if (match[v]==-1){
			res=1;
			continue ;
		}
		dist[match[v]]=dist[v]+1;
		Q.push(match[v]);
	}
	return res;
}

bool dfs(int node){
	mark[node]=1;
	for (int v:G[node]) if (match[v]==-1 || (dist[node]+1==dist[v] && !mark[match[v]] && dfs(match[v]))){
		match[v]=node;
		match[node]=v;
		return 1;
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++){
		cin>>A[i][j];
		if (A[i][j]=='1') id2[id[i][j]=cnt++]={i, j};
		else{
			int x=i, y=j;
			while (A[x][j]=='0') x--;
			while (A[i][y]=='0') y--;
			addedge(2*id[x][j], 2*id[i][y]+1);
		}
	}
	
	memset(match, -1, sizeof(match));
	while (BFS()){
		memset(mark, 0, sizeof(mark));
		for (int v=0; v<cnt; v++) if (!mark[2*v] && match[2*v]==-1) dfs(2*v);
	}
	
	for (int i=0; i<cnt; i++) if (match[2*i]!=-1){
		ans++;
		if (VC[2*i]) out[match[2*i]]=1;
		else out[2*i]=1;
	}
	cout<<ans<<'\n';
	for (int i=0; i<2*cnt; i++) if (out[i]){
		cout<<id2[i>>1].first<<' '<<id2[i>>1].second<<' ';
		if (i&1) cout<<"DESNO\n";
		else cout<<"DOLJE\n";
	}
	
	return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17664 KB Correct.
2 Correct 15 ms 17664 KB Correct.
3 Correct 15 ms 17664 KB Correct.
4 Correct 15 ms 17664 KB Correct.
5 Correct 14 ms 17664 KB Correct.
6 Correct 14 ms 17664 KB Correct.
7 Correct 14 ms 17664 KB Correct.
8 Correct 15 ms 17664 KB Correct.
9 Correct 15 ms 17664 KB Correct.
10 Correct 15 ms 17664 KB Correct.
11 Correct 14 ms 17664 KB Correct.
12 Correct 15 ms 17664 KB Correct.
13 Correct 15 ms 17664 KB Correct.
14 Correct 15 ms 17664 KB Correct.
15 Correct 14 ms 17664 KB Correct.
16 Correct 15 ms 17664 KB Correct.
17 Correct 14 ms 17664 KB Correct.
18 Correct 15 ms 17664 KB Correct.
19 Correct 15 ms 17664 KB Correct.
20 Correct 14 ms 17664 KB Correct.
21 Correct 16 ms 17664 KB Correct.
22 Correct 15 ms 17664 KB Correct.
23 Correct 16 ms 17664 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18816 KB Correct.
2 Correct 16 ms 18176 KB Correct.
3 Correct 17 ms 18560 KB Correct.
4 Correct 15 ms 18176 KB Correct.
5 Correct 15 ms 18048 KB Correct.
6 Correct 16 ms 18048 KB Correct.
7 Correct 16 ms 17920 KB Correct.
8 Correct 15 ms 18176 KB Correct.
9 Correct 17 ms 18944 KB Correct.
10 Correct 17 ms 19064 KB Correct.
11 Correct 16 ms 19072 KB Correct.
12 Correct 16 ms 19072 KB Correct.
13 Correct 16 ms 19072 KB Correct.
14 Correct 17 ms 19200 KB Correct.
15 Correct 18 ms 19072 KB Correct.
16 Correct 18 ms 19072 KB Correct.
17 Correct 16 ms 19072 KB Correct.
18 Correct 17 ms 19072 KB Correct.
19 Correct 16 ms 19072 KB Correct.
20 Correct 16 ms 19072 KB Correct.
21 Correct 16 ms 19072 KB Correct.
22 Correct 18 ms 19072 KB Correct.
23 Correct 17 ms 19072 KB Correct.
24 Correct 17 ms 18944 KB Correct.
25 Correct 17 ms 19072 KB Correct.
26 Correct 18 ms 19072 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17664 KB Correct.
2 Correct 15 ms 17664 KB Correct.
3 Correct 15 ms 17664 KB Correct.
4 Correct 15 ms 17664 KB Correct.
5 Correct 14 ms 17664 KB Correct.
6 Correct 14 ms 17664 KB Correct.
7 Correct 14 ms 17664 KB Correct.
8 Correct 15 ms 17664 KB Correct.
9 Correct 15 ms 17664 KB Correct.
10 Correct 15 ms 17664 KB Correct.
11 Correct 14 ms 17664 KB Correct.
12 Correct 15 ms 17664 KB Correct.
13 Correct 15 ms 17664 KB Correct.
14 Correct 15 ms 17664 KB Correct.
15 Correct 14 ms 17664 KB Correct.
16 Correct 15 ms 17664 KB Correct.
17 Correct 14 ms 17664 KB Correct.
18 Correct 15 ms 17664 KB Correct.
19 Correct 15 ms 17664 KB Correct.
20 Correct 14 ms 17664 KB Correct.
21 Correct 16 ms 17664 KB Correct.
22 Correct 15 ms 17664 KB Correct.
23 Correct 16 ms 17664 KB Correct.
24 Correct 15 ms 18816 KB Correct.
25 Correct 16 ms 18176 KB Correct.
26 Correct 17 ms 18560 KB Correct.
27 Correct 15 ms 18176 KB Correct.
28 Correct 15 ms 18048 KB Correct.
29 Correct 16 ms 18048 KB Correct.
30 Correct 16 ms 17920 KB Correct.
31 Correct 15 ms 18176 KB Correct.
32 Correct 17 ms 18944 KB Correct.
33 Correct 17 ms 19064 KB Correct.
34 Correct 16 ms 19072 KB Correct.
35 Correct 16 ms 19072 KB Correct.
36 Correct 16 ms 19072 KB Correct.
37 Correct 17 ms 19200 KB Correct.
38 Correct 18 ms 19072 KB Correct.
39 Correct 18 ms 19072 KB Correct.
40 Correct 16 ms 19072 KB Correct.
41 Correct 17 ms 19072 KB Correct.
42 Correct 16 ms 19072 KB Correct.
43 Correct 16 ms 19072 KB Correct.
44 Correct 16 ms 19072 KB Correct.
45 Correct 18 ms 19072 KB Correct.
46 Correct 17 ms 19072 KB Correct.
47 Correct 17 ms 18944 KB Correct.
48 Correct 17 ms 19072 KB Correct.
49 Correct 18 ms 19072 KB Correct.
50 Correct 62 ms 24196 KB Correct.
51 Correct 93 ms 22136 KB Correct.
52 Correct 88 ms 24308 KB Correct.
53 Correct 66 ms 24420 KB Correct.
54 Correct 68 ms 23504 KB Correct.
55 Correct 81 ms 25084 KB Correct.
56 Correct 69 ms 24824 KB Correct.
57 Correct 68 ms 24652 KB Correct.
58 Correct 91 ms 21880 KB Correct.
59 Correct 65 ms 23712 KB Correct.
60 Correct 78 ms 24488 KB Correct.
61 Correct 69 ms 23328 KB Correct.
62 Correct 74 ms 24416 KB Correct.
63 Correct 77 ms 24676 KB Correct.
64 Correct 97 ms 21368 KB Correct.
65 Correct 69 ms 24660 KB Correct.
66 Correct 77 ms 23668 KB Correct.
67 Correct 78 ms 24068 KB Correct.
68 Correct 75 ms 24936 KB Correct.
69 Correct 68 ms 24236 KB Correct.
70 Correct 67 ms 24380 KB Correct.
71 Correct 94 ms 24912 KB Correct.
72 Correct 77 ms 25300 KB Correct.
73 Correct 85 ms 25052 KB Correct.
74 Correct 80 ms 24568 KB Correct.
75 Correct 88 ms 25356 KB Correct.