Submission #167397

#	Time	Username	Problem	Language	Result	Execution time	Memory
167397		Trickster	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	6 ms	1912 KiB

shymbulak

//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()
{
	scanf("%d%d%d", &n, &m, &k);
	
	for(int i = 1; i <= k; i++) {
		scanf("%d%d", &a, &b);
		
		E[b].pb(a);
	}
	
	Q.push(0);
	int 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();
	}
	printf("%d", ans);
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(Q.size() > m) {
         ~~~~~~~~~^~~
shymbulak.cpp:68: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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp:71: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: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50