oj.uz

Submission #167398

# Submission time Handle Problem Language Result Execution time Memory
167398 2019-12-08T07:52:49 Z Trickster Marriage questions (IZhO14_marriage) C++14
40 / 100
 1500 ms 2056 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

marriage.cpp: In function 'int main()':
marriage.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(Q.size() > m) {
         ~~~~~~~~~^~~
marriage.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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
marriage.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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Incorrect 3 ms 1144 KB Output isn't correct
4 Incorrect 3 ms 1144 KB Output isn't correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Incorrect 75 ms 1272 KB Output isn't correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 2 ms 1016 KB Output is correct
11 Incorrect 3 ms 1144 KB Output isn't correct
12 Correct 3 ms 1144 KB Output is correct
13 Correct 3 ms 1144 KB Output is correct
14 Correct 3 ms 1144 KB Output is correct
15 Incorrect 3 ms 1144 KB Output isn't correct
16 Incorrect 3 ms 1144 KB Output isn't correct
17 Correct 3 ms 1144 KB Output is correct
18 Correct 3 ms 1144 KB Output is correct
19 Correct 4 ms 1144 KB Output is correct
20 Execution timed out 1567 ms 1144 KB Time limit exceeded
21 Correct 3 ms 1144 KB Output is correct
22 Incorrect 3 ms 1144 KB Output isn't correct
23 Correct 3 ms 1144 KB Output is correct
24 Correct 3 ms 1144 KB Output is correct
25 Execution timed out 1515 ms 1272 KB Time limit exceeded
26 Execution timed out 1554 ms 1212 KB Time limit exceeded
27 Correct 6 ms 1144 KB Output is correct
28 Incorrect 5 ms 1144 KB Output isn't correct
29 Execution timed out 1544 ms 1144 KB Time limit exceeded
30 Execution timed out 1523 ms 1148 KB Time limit exceeded
31 Execution timed out 1561 ms 1400 KB Time limit exceeded
32 Execution timed out 1566 ms 1144 KB Time limit exceeded
33 Correct 6 ms 1144 KB Output is correct
34 Incorrect 6 ms 1144 KB Output isn't correct
35 Correct 37 ms 1612 KB Output is correct
36 Correct 31 ms 1656 KB Output is correct
37 Execution timed out 1573 ms 1528 KB Time limit exceeded
38 Execution timed out 1583 ms 1656 KB Time limit exceeded
39 Incorrect 51 ms 1272 KB Output isn't correct
40 Correct 53 ms 1272 KB Output is correct
41 Execution timed out 1566 ms 1400 KB Time limit exceeded
42 Execution timed out 1575 ms 1400 KB Time limit exceeded
43 Execution timed out 1564 ms 1528 KB Time limit exceeded
44 Execution timed out 1569 ms 1784 KB Time limit exceeded
45 Execution timed out 1576 ms 1788 KB Time limit exceeded
46 Incorrect 341 ms 2056 KB Output isn't correct
47 Execution timed out 1570 ms 1784 KB Time limit exceeded
48 Execution timed out 1562 ms 1784 KB Time limit exceeded
49 Execution timed out 1560 ms 1784 KB Time limit exceeded
50 Incorrect 185 ms 1272 KB Output isn't correct