oj.uz

Submission #42733

# Submission time Handle Problem Language Result Execution time Memory
42733 2018-03-03T11:02:56 Z AryanSM Planinarenje (COCI18_planinarenje) C++14
160 / 160
 11 ms 6568 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
int const M=2e5+10;
int match[M],match2[M];
vector<int>adj[M];
bool good[M],mark[M];
bool dfs(int v)
{
	mark[v]=1;
	for(int i=0;i<adj[v].size();i++)
	{
		int u=adj[v][i];
		if(!match[u] || (!mark[match[u]] && dfs(match[u])))
		{
			match[u]=v;
			match2[v]=u;
			return 1;
		}
	}
	return 0;
}
void dfs_check(int v)
{
	good[v]=1;
	for(int i=0;i<adj[v].size();i++)
	{
		int u=adj[v][i];
		if(!good[match[u]])dfs_check(match[u]);
	}
}
main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		adj[a].pb(b);
	}
	while(true)
	{
		bool fin=0;
		for(int i=1;i<=n;i++)mark[i]=0;
		for(int i=1;i<=n;i++)
		{
			if(!mark[i] && !match2[i])
			{
				if(dfs(i))fin=1;
			}
		}
		if(!fin)break;
	}
	for(int i=1;i<=n;i++)
	{
		if(!match2[i])dfs_check(i);	
	}
	for(int i=1;i<=n;i++)
	{
		if(!good[i])cout<<"Slavko";
		else cout<<"Mirko";
		cout<<"\n";
	}
}

Compilation message

planinarenje.cpp: In function 'bool dfs(long long int)':
planinarenje.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[v].size();i++)
               ^
planinarenje.cpp: In function 'void dfs_check(long long int)':
planinarenje.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[v].size();i++)
               ^
planinarenje.cpp: At global scope:
planinarenje.cpp:37:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5328 KB Output is correct
2 Correct 5 ms 5328 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5328 KB Output is correct
2 Correct 5 ms 5328 KB Output is correct
3 Correct 5 ms 5352 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5356 KB Output is correct
2 Correct 5 ms 5368 KB Output is correct
3 Correct 5 ms 5476 KB Output is correct
4 Correct 5 ms 5520 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5780 KB Output is correct
2 Correct 9 ms 5864 KB Output is correct
3 Correct 9 ms 5864 KB Output is correct
4 Correct 9 ms 6000 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6000 KB Output is correct
2 Correct 8 ms 6000 KB Output is correct
3 Correct 6 ms 6000 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6000 KB Output is correct
2 Correct 7 ms 6000 KB Output is correct
3 Correct 6 ms 6000 KB Output is correct
4 Correct 8 ms 6000 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6116 KB Output is correct
2 Correct 9 ms 6172 KB Output is correct
3 Correct 9 ms 6212 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6264 KB Output is correct
2 Correct 11 ms 6444 KB Output is correct
3 Correct 6 ms 6444 KB Output is correct
4 Correct 8 ms 6444 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6444 KB Output is correct
2 Correct 6 ms 6488 KB Output is correct
3 Correct 9 ms 6520 KB Output is correct
4 Correct 9 ms 6568 KB Output is correct