oj.uz

Submission #464097

# Submission time Handle Problem Language Result Execution time Memory
464097 2021-08-12T11:39:43 Z Jasiekstrz Skandi (COCI20_skandi) C++17
110 / 110
 152 ms 34164 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=500;
bool t[N+10][N+10];
tuple<int,int,string> prnt[2][N*N+10];
int d[N+10][N+10];
int r[N+10][N+10];
bool vis[2][N*N+10];
int mtch[2][N*N+10];
vector<int> e[N*N+10];
bool dfs(int x)
{
	vis[0][x]=true;
	for(auto v:e[x])
	{
		if(vis[1][v])
			continue;
		vis[1][v]=true;
		if(mtch[1][v]==0 || (!vis[0][mtch[1][v]] && dfs(mtch[1][v])))
		{
			mtch[1][v]=x;
			mtch[0][x]=v;
			return true;
		}
	}
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char c;
			cin>>c;
			t[i][j]=(c=='1');
		}
	}
	int nd=0,nr=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			d[i][j]=d[i-1][j];
			r[i][j]=r[i][j-1];
			if(!t[i][j])
			{
				e[d[i][j]].push_back(r[i][j]);
			}
			else
			{
				if(i<n && !t[i+1][j])
				{
					nd++;
					prnt[0][nd]={i,j,"DOLJE"};
					d[i][j]=nd;
				}
				if(j<m && !t[i][j+1])
				{
					nr++;
					prnt[1][nr]={i,j,"DESNO"};
					r[i][j]=nr;
				}
			}
		}
	}
	bool con=true;
	while(con)
	{
		con=false;
		for(int i=1;i<=n*m;i++)
			vis[0][i]=vis[1][i]=false;
		for(int i=1;i<=nd;i++)
		{
			if(mtch[0][i]==0 && !vis[0][i] && dfs(i))
				con=true;
		}
	}
	vector<tuple<int,int,string>> ans;
	for(int i=1;i<=nd;i++)
	{
		if(!vis[0][i] && mtch[0][i]!=0)
			ans.push_back(prnt[0][i]);
	}
	for(int i=1;i<=nr;i++)
	{
		if(vis[1][i] && mtch[1][i]!=0)
			ans.push_back(prnt[1][i]);
	}
	cout<<ans.size()<<"\n";
	for(auto [a,b,c]:ans)
		cout<<a<<" "<<b<<" "<<c<<"\n";
	return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25704 KB Correct.
2 Correct 15 ms 25804 KB Correct.
3 Correct 14 ms 25708 KB Correct.
4 Correct 14 ms 25804 KB Correct.
5 Correct 14 ms 25676 KB Correct.
6 Correct 14 ms 25804 KB Correct.
7 Correct 14 ms 25804 KB Correct.
8 Correct 14 ms 25796 KB Correct.
9 Correct 14 ms 25748 KB Correct.
10 Correct 14 ms 25780 KB Correct.
11 Correct 14 ms 25812 KB Correct.
12 Correct 14 ms 25764 KB Correct.
13 Correct 14 ms 25768 KB Correct.
14 Correct 15 ms 25772 KB Correct.
15 Correct 15 ms 25720 KB Correct.
16 Correct 15 ms 25792 KB Correct.
17 Correct 15 ms 25788 KB Correct.
18 Correct 14 ms 25804 KB Correct.
19 Correct 14 ms 25804 KB Correct.
20 Correct 14 ms 25764 KB Correct.
21 Correct 15 ms 25804 KB Correct.
22 Correct 14 ms 25804 KB Correct.
23 Correct 14 ms 25776 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27596 KB Correct.
2 Correct 17 ms 26560 KB Correct.
3 Correct 15 ms 27340 KB Correct.
4 Correct 15 ms 26540 KB Correct.
5 Correct 14 ms 26468 KB Correct.
6 Correct 15 ms 26144 KB Correct.
7 Correct 16 ms 26088 KB Correct.
8 Correct 16 ms 26532 KB Correct.
9 Correct 16 ms 27980 KB Correct.
10 Correct 16 ms 28108 KB Correct.
11 Correct 18 ms 28108 KB Correct.
12 Correct 15 ms 28144 KB Correct.
13 Correct 17 ms 28156 KB Correct.
14 Correct 16 ms 28108 KB Correct.
15 Correct 16 ms 28128 KB Correct.
16 Correct 17 ms 28144 KB Correct.
17 Correct 17 ms 28080 KB Correct.
18 Correct 16 ms 28108 KB Correct.
19 Correct 16 ms 28108 KB Correct.
20 Correct 16 ms 28116 KB Correct.
21 Correct 16 ms 28172 KB Correct.
22 Correct 16 ms 28144 KB Correct.
23 Correct 16 ms 28120 KB Correct.
24 Correct 16 ms 28120 KB Correct.
25 Correct 16 ms 28072 KB Correct.
26 Correct 17 ms 28108 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25704 KB Correct.
2 Correct 15 ms 25804 KB Correct.
3 Correct 14 ms 25708 KB Correct.
4 Correct 14 ms 25804 KB Correct.
5 Correct 14 ms 25676 KB Correct.
6 Correct 14 ms 25804 KB Correct.
7 Correct 14 ms 25804 KB Correct.
8 Correct 14 ms 25796 KB Correct.
9 Correct 14 ms 25748 KB Correct.
10 Correct 14 ms 25780 KB Correct.
11 Correct 14 ms 25812 KB Correct.
12 Correct 14 ms 25764 KB Correct.
13 Correct 14 ms 25768 KB Correct.
14 Correct 15 ms 25772 KB Correct.
15 Correct 15 ms 25720 KB Correct.
16 Correct 15 ms 25792 KB Correct.
17 Correct 15 ms 25788 KB Correct.
18 Correct 14 ms 25804 KB Correct.
19 Correct 14 ms 25804 KB Correct.
20 Correct 14 ms 25764 KB Correct.
21 Correct 15 ms 25804 KB Correct.
22 Correct 14 ms 25804 KB Correct.
23 Correct 14 ms 25776 KB Correct.
24 Correct 15 ms 27596 KB Correct.
25 Correct 17 ms 26560 KB Correct.
26 Correct 15 ms 27340 KB Correct.
27 Correct 15 ms 26540 KB Correct.
28 Correct 14 ms 26468 KB Correct.
29 Correct 15 ms 26144 KB Correct.
30 Correct 16 ms 26088 KB Correct.
31 Correct 16 ms 26532 KB Correct.
32 Correct 16 ms 27980 KB Correct.
33 Correct 16 ms 28108 KB Correct.
34 Correct 18 ms 28108 KB Correct.
35 Correct 15 ms 28144 KB Correct.
36 Correct 17 ms 28156 KB Correct.
37 Correct 16 ms 28108 KB Correct.
38 Correct 16 ms 28128 KB Correct.
39 Correct 17 ms 28144 KB Correct.
40 Correct 17 ms 28080 KB Correct.
41 Correct 16 ms 28108 KB Correct.
42 Correct 16 ms 28108 KB Correct.
43 Correct 16 ms 28116 KB Correct.
44 Correct 16 ms 28172 KB Correct.
45 Correct 16 ms 28144 KB Correct.
46 Correct 16 ms 28120 KB Correct.
47 Correct 16 ms 28120 KB Correct.
48 Correct 16 ms 28072 KB Correct.
49 Correct 17 ms 28108 KB Correct.
50 Correct 48 ms 33180 KB Correct.
51 Correct 119 ms 30956 KB Correct.
52 Correct 65 ms 33596 KB Correct.
53 Correct 48 ms 33340 KB Correct.
54 Correct 53 ms 32936 KB Correct.
55 Correct 57 ms 33724 KB Correct.
56 Correct 49 ms 33512 KB Correct.
57 Correct 49 ms 33372 KB Correct.
58 Correct 152 ms 30976 KB Correct.
59 Correct 58 ms 33088 KB Correct.
60 Correct 62 ms 33392 KB Correct.
61 Correct 55 ms 33080 KB Correct.
62 Correct 52 ms 33304 KB Correct.
63 Correct 52 ms 33592 KB Correct.
64 Correct 58 ms 29892 KB Correct.
65 Correct 54 ms 33472 KB Correct.
66 Correct 53 ms 33036 KB Correct.
67 Correct 69 ms 33500 KB Correct.
68 Correct 54 ms 33768 KB Correct.
69 Correct 52 ms 33368 KB Correct.
70 Correct 51 ms 33428 KB Correct.
71 Correct 61 ms 33840 KB Correct.
72 Correct 52 ms 33832 KB Correct.
73 Correct 67 ms 34008 KB Correct.
74 Correct 60 ms 33856 KB Correct.
75 Correct 57 ms 34164 KB Correct.