oj.uz

답안 #392537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392537 2021-04-21T10:00:07 Z patrikpavic2 결혼 문제 (IZhO14_marriage) C++17
72 / 100
 1500 ms 12168 KB 
#include <cstdio>
#include <cstring>
#include <vector>

#define PB push_back

using namespace std;

typedef long long ll;

const int N = (1 << 15);

int par[N], n, m, bio[N], k, un[N];
vector < int > v[N], pos;

bool dodaj(int x){
	if(bio[x]) return 0;
	bio[x] = 1; pos.PB(x);
	for(int y : v[x]){
		if(un[y] && (par[y] == -1 || dodaj(par[y]))){
			par[x] = y; par[y] = x;
			return 1;
		}
	}
	return 0;
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 0;i < k;i++){
		int a, b; scanf("%d%d", &a, &b);
		a--; b--;
		v[a].PB(n + b), v[b + n].PB(a);
		//printf("VEZA %d %d\n", a, b + n);
	}
	memset(par, -1, sizeof(par));
	for(int i = 0;i < m;i++) un[i + n] = 1;
	int r = 0, sol = 0;
	ll ans = 0;
	for(int l = 0;l < n;l++){
		if(l){
			un[l - 1] = 0;
			if(par[l - 1] != -1){
				sol--; par[par[l - 1]] = -1;
				sol += dodaj(par[l - 1]);
				for(int x : pos) bio[x] = 0;
			}
		}		
		while(r < n && sol < m){
			un[r] = 1; sol += dodaj(r);
			for(int x : pos) bio[x] = 0;
			r++;
		}
		//printf("l = %d r = %d sol = %d\n", l, r, sol);
		ans += (n + 1 - r) * (sol == m);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
72.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1092 KB Output is correct
7 Correct 1 ms 1104 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct
13 Correct 1 ms 1184 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 1 ms 1100 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 5 ms 1296 KB Output is correct
20 Correct 3 ms 1228 KB Output is correct
21 Correct 1 ms 1100 KB Output is correct
22 Correct 1 ms 1100 KB Output is correct
23 Correct 3 ms 1228 KB Output is correct
24 Correct 2 ms 1228 KB Output is correct
25 Correct 128 ms 2112 KB Output is correct
26 Correct 87 ms 1600 KB Output is correct
27 Correct 2 ms 1100 KB Output is correct
28 Correct 7 ms 1228 KB Output is correct
29 Correct 52 ms 1692 KB Output is correct
30 Correct 70 ms 1656 KB Output is correct
31 Execution timed out 1588 ms 4384 KB Time limit exceeded
32 Correct 1100 ms 3512 KB Output is correct
33 Correct 5 ms 1228 KB Output is correct
34 Correct 385 ms 2400 KB Output is correct
35 Correct 1090 ms 4156 KB Output is correct
36 Correct 942 ms 3940 KB Output is correct
37 Execution timed out 1555 ms 6832 KB Time limit exceeded
38 Execution timed out 1569 ms 7460 KB Time limit exceeded
39 Execution timed out 1596 ms 5832 KB Time limit exceeded
40 Correct 814 ms 2128 KB Output is correct
41 Execution timed out 1593 ms 3072 KB Time limit exceeded
42 Execution timed out 1595 ms 4192 KB Time limit exceeded
43 Execution timed out 1576 ms 4544 KB Time limit exceeded
44 Execution timed out 1591 ms 7448 KB Time limit exceeded
45 Execution timed out 1585 ms 2984 KB Time limit exceeded
46 Execution timed out 1588 ms 7864 KB Time limit exceeded
47 Execution timed out 1562 ms 5740 KB Time limit exceeded
48 Execution timed out 1588 ms 5636 KB Time limit exceeded
49 Execution timed out 1591 ms 12168 KB Time limit exceeded
50 Execution timed out 1592 ms 5812 KB Time limit exceeded