oj.uz

Submission #392565

# Submission time Handle Problem Language Result Execution time Memory
392565 2021-04-21T10:36:38 Z patrikpavic2 Marriage questions (IZhO14_marriage) C++17
10 / 100
 48 ms 5764 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

# Verdict Execution time Memory 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 2 ms 2124 KB Execution killed with signal 11
4 Incorrect 1 ms 1100 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 2124 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 2 ms 2128 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 3 ms 2212 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 3 ms 2252 KB Execution killed with signal 11
24 Runtime error 2 ms 2124 KB Execution killed with signal 11
25 Runtime error 7 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 48 ms 3504 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 27 ms 4328 KB Execution killed with signal 11
36 Runtime error 23 ms 4236 KB Execution killed with signal 11
37 Runtime error 22 ms 3764 KB Execution killed with signal 11
38 Runtime error 28 ms 4764 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 3160 KB Execution killed with signal 11
42 Incorrect 10 ms 1904 KB Output isn't correct
43 Incorrect 19 ms 1944 KB Output isn't correct
44 Incorrect 29 ms 2416 KB Output isn't correct
45 Runtime error 16 ms 4172 KB Execution killed with signal 11
46 Runtime error 41 ms 5512 KB Execution killed with signal 11
47 Incorrect 29 ms 2932 KB Output isn't correct
48 Incorrect 28 ms 2884 KB Output isn't correct
49 Runtime error 43 ms 5764 KB Execution killed with signal 11
50 Incorrect 3 ms 1488 KB Output isn't correct