oj.uz

Submission #825532

# Submission time Handle Problem Language Result Execution time Memory
825532 2023-08-15T02:12:31 Z jamezzz Planinarenje (COCI18_planinarenje) C++17
160 / 160
 27 ms 948 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar_unlocked();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 10005

int n,m,rem[maxn],match[maxn];
bool used[maxn];
vi AL[maxn];

bool dfs(int u){
	if(used[u])return false;
	used[u]=true;
	for(int v:AL[u]){
		if(rem[v])continue;
		if(match[v]==-1||dfs(match[v])){
			match[v]=u;
			return true;
		}
	}
	return false;
}

bool augment(int i){
	memset(used,false,sizeof used);
	return dfs(i);
}

int main(){
	sf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		int a,b;sf("%d%d",&a,&b);
		b+=n;
		AL[a].pb(b);
		AL[b].pb(a);
	}
	memset(match,-1,sizeof match);
	for(int i=n+1;i<=2*n;++i){
		augment(i);
	}
	for(int i=1;i<=n;++i){
		if(match[i]==-1){
			pf("Mirko\n");
			continue;
		}
		int tmp=match[i];
		match[i]=-1;
		rem[i]=true;
		if(augment(tmp)){
			rem[i]=false;
			pf("Mirko\n");
		}
		else{
			rem[i]=false;
			augment(tmp);
			pf("Slavko\n");
		}
	}
}

Compilation message

planinarenje.cpp: In function 'int main()':
planinarenje.cpp:87:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |  sf("%d%d",&n,&m);
      |    ^
planinarenje.cpp:89:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   int a,b;sf("%d%d",&a,&b);
      |             ^

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 1 ms 596 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 948 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 692 KB Output is correct
2 Correct 13 ms 680 KB Output is correct
3 Correct 6 ms 692 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 8 ms 688 KB Output is correct
4 Correct 9 ms 744 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 816 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 788 KB Output is correct
2 Correct 3 ms 820 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 27 ms 756 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 812 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 9 ms 724 KB Output is correct