Submission #167176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167176	2019-12-06T08:05:45 Z	Trickster	Marriage questions (IZhO14_marriage)	C++14	24 / 100	1500 ms	4408 KB

marriage

//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)
{
	int ret = 1;
	pii vis[N];
	
	for(int i = 1; i <= max(n, m); i++) vis[i] = {0, 0};
	
	vector <int> S[N];
	for(int i = l; i <= r; i++)
		for(auto h: E[i])
			S[h].pb(i);
	
	for(int i = 1; i <= m; i++) {
		if(S[i].size() == 1 && vis[S[i][0]].ss == 0) vis[i].ff = 1, vis[S[i][0]].ss = 1;
		if(S[i].size() == 0) ret = 0;
	}
	
	for(int i = l; i <= r; i++)
		if(E[i].size() == 1) {
			vis[i].ss = 1;
			vis[E[i][0]].ff = 1;
		}
	
	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;
	
	return ret;
}

int main()
{
	cin >> n >> m >> k;
	
	for(int i = 1; i <= k; i++) {
		cin >> 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 l = Q.front();
		
		int ok = tap(l, i);
		
		if(ok == 1) {
			ans++;
			pos = i;
			break;
		}
	}
	
	for(int i = pos+1; 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();
	}
	cout << ans;
}

Compilation message

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

Subtask #1

24.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	2040 KB	Output isn't correct
2	Incorrect	8 ms	1916 KB	Output isn't correct
3	Correct	4 ms	1912 KB	Output is correct
4	Incorrect	5 ms	2012 KB	Output isn't correct
5	Correct	5 ms	2000 KB	Output is correct
6	Correct	4 ms	2040 KB	Output is correct
7	Incorrect	6 ms	1912 KB	Output isn't correct
8	Correct	3 ms	1916 KB	Output is correct
9	Incorrect	4 ms	1912 KB	Output isn't correct
10	Incorrect	4 ms	2040 KB	Output isn't correct
11	Correct	4 ms	2040 KB	Output is correct
12	Incorrect	4 ms	1912 KB	Output isn't correct
13	Correct	5 ms	1912 KB	Output is correct
14	Incorrect	6 ms	1912 KB	Output isn't correct
15	Incorrect	6 ms	1912 KB	Output isn't correct
16	Incorrect	7 ms	2040 KB	Output isn't correct
17	Correct	5 ms	1912 KB	Output is correct
18	Correct	5 ms	1912 KB	Output is correct
19	Incorrect	26 ms	2040 KB	Output isn't correct
20	Incorrect	17 ms	2040 KB	Output isn't correct
21	Incorrect	24 ms	1912 KB	Output isn't correct
22	Incorrect	23 ms	2012 KB	Output isn't correct
23	Correct	15 ms	2072 KB	Output is correct
24	Correct	39 ms	2168 KB	Output is correct
25	Incorrect	149 ms	2168 KB	Output isn't correct
26	Incorrect	109 ms	2040 KB	Output isn't correct
27	Incorrect	112 ms	2176 KB	Output isn't correct
28	Incorrect	106 ms	1912 KB	Output isn't correct
29	Incorrect	103 ms	2176 KB	Output isn't correct
30	Incorrect	99 ms	2168 KB	Output isn't correct
31	Incorrect	929 ms	2972 KB	Output isn't correct
32	Incorrect	434 ms	2176 KB	Output isn't correct
33	Incorrect	244 ms	2040 KB	Output isn't correct
34	Incorrect	253 ms	2180 KB	Output isn't correct
35	Correct	1020 ms	3908 KB	Output is correct
36	Correct	962 ms	3768 KB	Output is correct
37	Execution timed out	1540 ms	2972 KB	Time limit exceeded
38	Execution timed out	1570 ms	4188 KB	Time limit exceeded
39	Execution timed out	1563 ms	2368 KB	Time limit exceeded
40	Execution timed out	1540 ms	2696 KB	Time limit exceeded
41	Execution timed out	1517 ms	2680 KB	Time limit exceeded
42	Execution timed out	1560 ms	2808 KB	Time limit exceeded
43	Execution timed out	1533 ms	3212 KB	Time limit exceeded
44	Execution timed out	1557 ms	3920 KB	Time limit exceeded
45	Execution timed out	1536 ms	3204 KB	Time limit exceeded
46	Execution timed out	1555 ms	4096 KB	Time limit exceeded
47	Execution timed out	1542 ms	4228 KB	Time limit exceeded
48	Execution timed out	1541 ms	4200 KB	Time limit exceeded
49	Execution timed out	1557 ms	4408 KB	Time limit exceeded
50	Execution timed out	1567 ms	2424 KB	Time limit exceeded