Submission #167176

#	Time	Username	Problem	Language	Result	Execution time	Memory
167176		Trickster	결혼 문제 (IZhO14_marriage)	C++14	24 / 100	1570 ms	4408 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)
{
	int ret = 1;
	pii vis[N];
	
	for(int i = 1; i <= max(n, m); i++) vis[i] = {0, 0};
	
	vector <int> S[N];
	for(int i = l; i <= r; i++)
		for(auto h: E[i])
			S[h].pb(i);
	
	for(int i = 1; i <= m; i++) {
		if(S[i].size() == 1 && vis[S[i][0]].ss == 0) vis[i].ff = 1, vis[S[i][0]].ss = 1;
		if(S[i].size() == 0) ret = 0;
	}
	
	for(int i = l; i <= r; i++)
		if(E[i].size() == 1) {
			vis[i].ss = 1;
			vis[E[i][0]].ff = 1;
		}
	
	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;
	
	return ret;
}

int main()
{
	cin >> n >> m >> k;
	
	for(int i = 1; i <= k; i++) {
		cin >> 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 l = Q.front();
		
		int ok = tap(l, i);
		
		if(ok == 1) {
			ans++;
			pos = i;
			break;
		}
	}
	
	for(int i = pos+1; 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();
	}
	cout << ans;
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(Q.size() > m) {
         ~~~~~~~~~^~~

• Subtask 1: 24 / 100