oj.uz

Submission #167391

# Submission time Handle Problem Language Result Execution time Memory
167391 2019-12-08T06:47:53 Z Trickster Marriage questions (IZhO14_marriage) C++14
22 / 100
 1500 ms 262148 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 a, b;
int n, m, k;
vector <int> E[N];

int tap(int l, int r)
{
	pii vis[N];
	int ret = 1;
	vector <int> S[N];
	vector <int> T[N];
	for(int i = 1; i <= max(n, m); i++) vis[i] = {0, 0};
	
	for(int i = l; i <= r; i++)
		for(auto h: E[i])
			S[h].pb(i), T[i].pb(h);
	
	while(1) {
		int ok = 0;
		
		for(int i = l; i <= r; i++) {
			if(E[i].size() == 1) vis[i].ss = vis[E[i][0]].ff = ok = 1;
			E[i].clear();
		}
		
		for(int i = 1; i <= m; i++) {
			if(vis[i].ff == 1) continue;
			
			if(S[i].size() == 0) ret = 0;
			if(S[i].size() == 1 && vis[S[i][0]].ss == 0) vis[i].ff = vis[S[i][0]].ss = ok = 1;
			
			S[i].clear();
		}
		
		for(int i = l; i <= r; i++) {
			if(vis[i].ss == 1) continue;
			
			for(auto h: T[i])
				if(vis[h].ss == 0) S[h].pb(i), E[i].pb(h);
		}
		
		if(ok == 0) break;
	}
	
	for(int i = 1; i <= m; i++) {
		if(vis[i].ff == 1) continue;
		
		for(auto h: S[i])
			if(vis[h].ss == 0) {
				vis[i].ff = vis[h].ss = 1;
				break;
			}
	}
	
	for(int i = 1; i <= m; i++)
		if(vis[i].ff == 0) ret = 0;
	
	for(int i = l; i <= r; i++)
		for(auto h: T[i])
			E[i].pb(h);
	
	return ret;
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	
	for(int i = 1; i <= k; i++) {
		scanf("%d%d", &a, &b);
		
		E[a].pb(b);
	}
	
	queue <int> Q;
	int ans = 0, pos = 0;
	for(int i = 1; i <= n; i++) {
		Q.push(i);
		
		int ok = tap(1, i);
		
		if(ok == 1) {
			ans ++;
			pos = i+1;
			break;
		}
	}
	if(pos == 0) {
		cout << 0;
		return 0;
	}
	
	for(int i = pos; i <= n; i++) {
		Q.push(i);
		
		while(Q.size() > m) {
			int l = Q.front();
			
			int ok = tap(l+1, i);
			
			if(ok == 0) break;
			
			Q.pop();
		}
		
		ans += Q.front();
	}
	printf("%d", ans);
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2680 KB Output isn't correct
2 Incorrect 6 ms 2680 KB Output isn't correct
3 Correct 6 ms 2680 KB Output is correct
4 Incorrect 6 ms 2680 KB Output isn't correct
5 Correct 6 ms 2680 KB Output is correct
6 Correct 6 ms 2680 KB Output is correct
7 Incorrect 76 ms 13744 KB Output isn't correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 5 ms 2684 KB Output is correct
10 Correct 5 ms 2680 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 5 ms 2680 KB Output is correct
13 Correct 6 ms 2680 KB Output is correct
14 Incorrect 77 ms 14872 KB Output isn't correct
15 Incorrect 8 ms 2680 KB Output isn't correct
16 Incorrect 8 ms 2680 KB Output isn't correct
17 Correct 9 ms 2908 KB Output is correct
18 Correct 9 ms 2936 KB Output is correct
19 Execution timed out 1562 ms 233952 KB Time limit exceeded
20 Runtime error 1451 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Execution timed out 1585 ms 244728 KB Time limit exceeded
22 Incorrect 25 ms 2680 KB Output isn't correct
23 Execution timed out 1588 ms 232936 KB Time limit exceeded
24 Execution timed out 1582 ms 232004 KB Time limit exceeded
25 Runtime error 1268 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Execution timed out 1573 ms 171360 KB Time limit exceeded
27 Execution timed out 1578 ms 262148 KB Time limit exceeded
28 Incorrect 212 ms 2652 KB Output isn't correct
29 Runtime error 1476 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 1441 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Execution timed out 1583 ms 210336 KB Time limit exceeded
32 Execution timed out 1587 ms 200360 KB Time limit exceeded
33 Runtime error 1384 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Execution timed out 1561 ms 2808 KB Time limit exceeded
35 Execution timed out 1568 ms 4528 KB Time limit exceeded
36 Execution timed out 1559 ms 4372 KB Time limit exceeded
37 Execution timed out 1569 ms 123904 KB Time limit exceeded
38 Execution timed out 1581 ms 106460 KB Time limit exceeded
39 Execution timed out 1564 ms 3060 KB Time limit exceeded
40 Execution timed out 1574 ms 241376 KB Time limit exceeded
41 Execution timed out 1572 ms 200500 KB Time limit exceeded
42 Runtime error 1457 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
43 Execution timed out 1575 ms 260440 KB Time limit exceeded
44 Runtime error 1483 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Execution timed out 1560 ms 217396 KB Time limit exceeded
46 Execution timed out 1585 ms 218244 KB Time limit exceeded
47 Execution timed out 1558 ms 224916 KB Time limit exceeded
48 Execution timed out 1583 ms 259436 KB Time limit exceeded
49 Execution timed out 1592 ms 203968 KB Time limit exceeded
50 Execution timed out 1566 ms 2936 KB Time limit exceeded