Submission #167391

#	Time	Username	Problem	Language	Result	Execution time	Memory
167391		Trickster	결혼 문제 (IZhO14_marriage)	C++14	22 / 100	1592 ms	262148 KiB

marriage

//Suleyman Atayew

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define N 30010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define inf 1000000007
#define pii pair <int, int>

using namespace std;

int a, b;
int n, m, k;
vector <int> E[N];

int tap(int l, int r)
{
	pii vis[N];
	int ret = 1;
	vector <int> S[N];
	vector <int> T[N];
	for(int i = 1; i <= max(n, m); i++) vis[i] = {0, 0};
	
	for(int i = l; i <= r; i++)
		for(auto h: E[i])
			S[h].pb(i), T[i].pb(h);
	
	while(1) {
		int ok = 0;
		
		for(int i = l; i <= r; i++) {
			if(E[i].size() == 1) vis[i].ss = vis[E[i][0]].ff = ok = 1;
			E[i].clear();
		}
		
		for(int i = 1; i <= m; i++) {
			if(vis[i].ff == 1) continue;
			
			if(S[i].size() == 0) ret = 0;
			if(S[i].size() == 1 && vis[S[i][0]].ss == 0) vis[i].ff = vis[S[i][0]].ss = ok = 1;
			
			S[i].clear();
		}
		
		for(int i = l; i <= r; i++) {
			if(vis[i].ss == 1) continue;
			
			for(auto h: T[i])
				if(vis[h].ss == 0) S[h].pb(i), E[i].pb(h);
		}
		
		if(ok == 0) break;
	}
	
	for(int i = 1; i <= m; i++) {
		if(vis[i].ff == 1) continue;
		
		for(auto h: S[i])
			if(vis[h].ss == 0) {
				vis[i].ff = vis[h].ss = 1;
				break;
			}
	}
	
	for(int i = 1; i <= m; i++)
		if(vis[i].ff == 0) ret = 0;
	
	for(int i = l; i <= r; i++)
		for(auto h: T[i])
			E[i].pb(h);
	
	return ret;
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	
	for(int i = 1; i <= k; i++) {
		scanf("%d%d", &a, &b);
		
		E[a].pb(b);
	}
	
	queue <int> Q;
	int ans = 0, pos = 0;
	for(int i = 1; i <= n; i++) {
		Q.push(i);
		
		int ok = tap(1, i);
		
		if(ok == 1) {
			ans ++;
			pos = i+1;
			break;
		}
	}
	if(pos == 0) {
		cout << 0;
		return 0;
	}
	
	for(int i = pos; i <= n; i++) {
		Q.push(i);
		
		while(Q.size() > m) {
			int l = Q.front();
			
			int ok = tap(l+1, i);
			
			if(ok == 0) break;
			
			Q.pop();
		}
		
		ans += Q.front();
	}
	printf("%d", ans);
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:117:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(Q.size() > m) {
         ~~~~~~~~~^~~
marriage.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 22 / 100