oj.uz

답안 #167397

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167397 2019-12-08T07:52:40 Z Trickster 관광지 (IZhO14_shymbulak) C++14
0 / 100
 6 ms 1912 KB 
//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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -