oj.uz

Submission #167396

# Submission time Handle Problem Language Result Execution time Memory
167396 2019-12-08T07:51:19 Z Trickster Marriage questions (IZhO14_marriage) C++14
40 / 100
 1500 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()
{
	cin >> n >> m >> k;
	
	for(int i = 1; i <= k; i++) {
		cin >> a >> b;
		
		E[b].pb(a);
	}
	
	Q.push(0);
	ll 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();
	}
	cout << 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) {
         ~~~~~~~~~^~~

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 1148 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 62 ms 1144 KB Output isn't correct
8 Correct 3 ms 1272 KB Output is correct
9 Correct 3 ms 1148 KB Output is correct
10 Correct 3 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 7 ms 1144 KB Output is correct
15 Incorrect 3 ms 1144 KB Output isn't correct
16 Incorrect 3 ms 1148 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 5 ms 1144 KB Output is correct
20 Execution timed out 1507 ms 1144 KB Time limit exceeded
21 Correct 4 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 1559 ms 1144 KB Time limit exceeded
26 Execution timed out 1566 ms 1244 KB Time limit exceeded
27 Correct 6 ms 1148 KB Output is correct
28 Incorrect 5 ms 1144 KB Output isn't correct
29 Execution timed out 1555 ms 1272 KB Time limit exceeded
30 Execution timed out 1571 ms 1272 KB Time limit exceeded
31 Execution timed out 1565 ms 1400 KB Time limit exceeded
32 Execution timed out 1510 ms 1144 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 92 ms 1784 KB Output is correct
36 Correct 75 ms 1784 KB Output is correct
37 Execution timed out 1559 ms 1656 KB Time limit exceeded
38 Execution timed out 1505 ms 1636 KB Time limit exceeded
39 Incorrect 54 ms 1276 KB Output isn't correct
40 Correct 59 ms 1272 KB Output is correct
41 Execution timed out 1541 ms 1500 KB Time limit exceeded
42 Execution timed out 1559 ms 1400 KB Time limit exceeded
43 Execution timed out 1574 ms 1528 KB Time limit exceeded
44 Execution timed out 1548 ms 1784 KB Time limit exceeded
45 Execution timed out 1554 ms 1532 KB Time limit exceeded
46 Incorrect 394 ms 1912 KB Output isn't correct
47 Execution timed out 1570 ms 1912 KB Time limit exceeded
48 Execution timed out 1524 ms 1784 KB Time limit exceeded
49 Execution timed out 1546 ms 1784 KB Time limit exceeded
50 Incorrect 180 ms 1400 KB Output isn't correct