Submission #167982

#	Time	Username	Problem	Language	Result	Execution time	Memory
167982		Trickster	Marriage questions (IZhO14_marriage)	C++14	100 / 100	892 ms	2780 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 now;
int a, b;
int l, r;
int T[N];
int v[N];
int n, m, k;
queue <int> Q;
vector <int> E[N];

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

void tap()
{
	while(Q.size()) {
		int a = Q.front();
		Q.pop(), now++;
		
		if(!dfs(a)) {
			Q.push(a);
			break;
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	
	for(int i = 1; i <= k; i++) {
		scanf("%d%d", &a, &b);
		
		E[b].pb(a);
	}
	
	for(int i = 1; i <= m; i++) Q.push(i);
	
	int ans = 0;
	for(l = 1; l <= n; l++) {
		r = max(r, l);
		tap();
		
		while(r < n && Q.size()) r++, tap();
		
		if(Q.size()) break;
		
		ans += n-r+1;
		
		if(T[l]) Q.push(T[l]), T[l] = 0;
	}
	printf("%d", ans);
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:60: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:63: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: 100 / 100