oj.uz

Submission #167395

# Submission time Handle Problem Language Result Execution time Memory
167395 2019-12-08T07:47:13 Z Trickster Marriage questions (IZhO14_marriage) C++14
38 / 100
 1500 ms 2524 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;
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;
		}
	else if(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);
	}
	
	int ans = 0;
	queue <int> Q;
	
	Q.push(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;
}

Compilation message

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

Subtask #1
38.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 1148 KB Output is correct
6 Correct 3 ms 1148 KB Output is correct
7 Incorrect 61 ms 1148 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 3 ms 1016 KB Output is correct
11 Incorrect 2 ms 1144 KB Output isn't correct
12 Correct 3 ms 1144 KB Output is correct
13 Incorrect 3 ms 1144 KB Output isn't correct
14 Correct 3 ms 1144 KB Output is correct
15 Incorrect 3 ms 1148 KB Output isn't correct
16 Incorrect 3 ms 1144 KB Output isn't correct
17 Correct 3 ms 1148 KB Output is correct
18 Correct 3 ms 1144 KB Output is correct
19 Correct 5 ms 1144 KB Output is correct
20 Execution timed out 1576 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 4 ms 1144 KB Output is correct
24 Correct 4 ms 1144 KB Output is correct
25 Execution timed out 1583 ms 1272 KB Time limit exceeded
26 Execution timed out 1576 ms 1144 KB Time limit exceeded
27 Correct 7 ms 1144 KB Output is correct
28 Incorrect 5 ms 1148 KB Output isn't correct
29 Execution timed out 1566 ms 1288 KB Time limit exceeded
30 Execution timed out 1576 ms 1272 KB Time limit exceeded
31 Execution timed out 1582 ms 1400 KB Time limit exceeded
32 Execution timed out 1571 ms 1148 KB Time limit exceeded
33 Correct 6 ms 1144 KB Output is correct
34 Incorrect 7 ms 1144 KB Output isn't correct
35 Correct 91 ms 1656 KB Output is correct
36 Correct 75 ms 1784 KB Output is correct
37 Execution timed out 1558 ms 1528 KB Time limit exceeded
38 Execution timed out 1591 ms 1656 KB Time limit exceeded
39 Incorrect 54 ms 1272 KB Output isn't correct
40 Correct 60 ms 1400 KB Output is correct
41 Execution timed out 1579 ms 1504 KB Time limit exceeded
42 Execution timed out 1585 ms 1656 KB Time limit exceeded
43 Execution timed out 1581 ms 1528 KB Time limit exceeded
44 Execution timed out 1578 ms 2524 KB Time limit exceeded
45 Execution timed out 1575 ms 1536 KB Time limit exceeded
46 Incorrect 257 ms 1980 KB Output isn't correct
47 Execution timed out 1562 ms 1888 KB Time limit exceeded
48 Execution timed out 1579 ms 1912 KB Time limit exceeded
49 Execution timed out 1583 ms 2056 KB Time limit exceeded
50 Incorrect 173 ms 1392 KB Output isn't correct