oj.uz

답안 #392567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392567 2021-04-21T10:36:56 Z patrikpavic2 결혼 문제 (IZhO14_marriage) C++17
10 / 100
 40 ms 5700 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
 
#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], cookie = 1;
int poc[N], deg[N];
vector < int > v[N];
  
bool dodaj(int x){
	if(bio[x] == cookie) return 0;
	bio[x] = cookie;
	for(int i = poc[x];i < deg[i] && un[v[x][i]];i++){
		if(par[v[x][i]] == -1 || dodaj(par[v[x][i]])){
			par[x] = v[x][i]; par[v[x][i]] = 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);
		deg[a]++; deg[b + n]++;
	}
	memset(par, -1, sizeof(par));
	for(int i = 0;i < m;i++){
		un[i + n] = 1;
		sort(v[i + n].begin(), v[i + n].end());
	}
	int r = 0, sol = 0;
	ll ans = 0;
	for(int l = 0;l < n;l++){
		if(l && sol == m){
			un[l - 1] = 0;
			//for(int i = n;i < m + n;i++)
			//	if(poc[i] < deg[i] && v[i][poc[i]] < l) poc[i]++;
			if(par[l - 1] != -1){
				sol--; par[par[l - 1]] = -1;
				sol += dodaj(par[l - 1]); cookie++;
			}
		}		
		while(r < n && sol < m){
			un[r] = 1; sol += dodaj(r); cookie++;
			r++;
		}
		ans += (n + 1 - r) * (sol == m);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1100 KB Output isn't correct
2 Incorrect 1 ms 1100 KB Output isn't correct
3 Runtime error 3 ms 2128 KB Execution killed with signal 11
4 Incorrect 1 ms 1104 KB Output isn't correct
5 Runtime error 2 ms 2124 KB Execution killed with signal 11
6 Runtime error 2 ms 2124 KB Execution killed with signal 11
7 Incorrect 1 ms 1100 KB Output isn't correct
8 Correct 1 ms 1100 KB Output is correct
9 Runtime error 2 ms 2100 KB Execution killed with signal 11
10 Correct 1 ms 1100 KB Output is correct
11 Incorrect 1 ms 1100 KB Output isn't correct
12 Correct 1 ms 1100 KB Output is correct
13 Runtime error 2 ms 2124 KB Execution killed with signal 11
14 Runtime error 3 ms 2124 KB Execution killed with signal 11
15 Incorrect 1 ms 1100 KB Output isn't correct
16 Incorrect 1 ms 1100 KB Output isn't correct
17 Runtime error 2 ms 2124 KB Execution killed with signal 11
18 Runtime error 2 ms 2124 KB Execution killed with signal 11
19 Correct 2 ms 1228 KB Output is correct
20 Incorrect 1 ms 1100 KB Output isn't correct
21 Runtime error 2 ms 2124 KB Execution killed with signal 11
22 Incorrect 1 ms 1100 KB Output isn't correct
23 Runtime error 2 ms 2252 KB Execution killed with signal 11
24 Runtime error 2 ms 2124 KB Execution killed with signal 11
25 Runtime error 6 ms 2508 KB Execution killed with signal 11
26 Runtime error 3 ms 2252 KB Execution killed with signal 11
27 Correct 1 ms 1100 KB Output is correct
28 Incorrect 1 ms 1100 KB Output isn't correct
29 Incorrect 3 ms 1228 KB Output isn't correct
30 Incorrect 3 ms 1228 KB Output isn't correct
31 Runtime error 20 ms 3424 KB Execution killed with signal 11
32 Runtime error 4 ms 2380 KB Execution killed with signal 11
33 Runtime error 2 ms 2252 KB Execution killed with signal 11
34 Incorrect 1 ms 1228 KB Output isn't correct
35 Runtime error 26 ms 4388 KB Execution killed with signal 11
36 Runtime error 23 ms 4388 KB Execution killed with signal 11
37 Runtime error 20 ms 3756 KB Execution killed with signal 11
38 Runtime error 27 ms 4776 KB Execution killed with signal 11
39 Incorrect 2 ms 1356 KB Output isn't correct
40 Runtime error 6 ms 2764 KB Execution killed with signal 11
41 Runtime error 10 ms 3148 KB Execution killed with signal 11
42 Incorrect 10 ms 1908 KB Output isn't correct
43 Incorrect 14 ms 1996 KB Output isn't correct
44 Incorrect 25 ms 2408 KB Output isn't correct
45 Runtime error 14 ms 4060 KB Execution killed with signal 11
46 Runtime error 36 ms 5560 KB Execution killed with signal 11
47 Incorrect 28 ms 2944 KB Output isn't correct
48 Incorrect 26 ms 2864 KB Output isn't correct
49 Runtime error 40 ms 5700 KB Execution killed with signal 11
50 Incorrect 3 ms 1536 KB Output isn't correct