oj.uz

답안 #167176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167176 2019-12-06T08:05:45 Z Trickster 결혼 문제 (IZhO14_marriage) C++14
24 / 100
 1500 ms 4408 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)
{
	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

# 결과 실행 시간 메모리 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