제출 #167396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167396		Trickster	결혼 문제 (IZhO14_marriage)	C++14	40 / 100	1574 ms	1912 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 T[N];
int a, b;
int vis[N];
int n, m, k;
queue <int> Q;
vector <int> E[N];

int dfs(int x, int l, int r)
{
	for(auto i: E[x])
		if(vis[i] == 0 && i >= l && i <= r) {
			if(T[i] == 0) {
				vis[i] = 1;
				T[i] = x;
				return 1;
			}
			else {
				int y = T[i];
				vis[i] = 1;
				T[i] = x;
				
				if(dfs(y, l, r) == 1) return 1;
				
				T[i] = y;
				vis[i] = 0;
			}
		}
	return 0;
}

int tap(int l, int r)
{
	memset(vis, 0, sizeof(vis));
	
	if(l == 0)
		for(int i = 1; i <= m; i++)
			if(dfs(i, l+1, r) == 0) return 0;
	
	if(l && T[l] && dfs(T[l], l+1, r) == 0) return 0;
	
	return 1;
}

int main()
{
	cin >> n >> m >> k;
	
	for(int i = 1; i <= k; i++) {
		cin >> a >> b;
		
		E[b].pb(a);
	}
	
	Q.push(0);
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		Q.push(i);
		
		while(Q.size() > m) {
			int l = Q.front();
			
			int ok = tap(l, i);
			
			if(ok == 0) break;
			
			Q.pop();
		}
		
		ans += Q.front();
	}
	cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 40 / 100