oj.uz

Submission #392563

# Submission time Handle Problem Language Result Execution time Memory
392563 2021-04-21T10:35:33 Z patrikpavic2 Marriage questions (IZhO14_marriage) C++17
10 / 100
 49 ms 6524 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[n + b]++;
	}
	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] && !un[v[i][poc[i]]]) 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 1240 KB Output isn't correct
3 Runtime error 3 ms 2304 KB Execution killed with signal 11
4 Incorrect 1 ms 1184 KB Output isn't correct
5 Runtime error 2 ms 2220 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 1104 KB Output isn't correct
12 Correct 1 ms 1100 KB Output is correct
13 Runtime error 2 ms 2128 KB Execution killed with signal 11
14 Runtime error 2 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 3 ms 2252 KB Execution killed with signal 11
24 Runtime error 2 ms 2128 KB Execution killed with signal 11
25 Runtime error 7 ms 2644 KB Execution killed with signal 11
26 Runtime error 3 ms 2272 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 1324 KB Output isn't correct
30 Incorrect 3 ms 1228 KB Output isn't correct
31 Runtime error 49 ms 3780 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 1188 KB Output isn't correct
35 Runtime error 26 ms 5060 KB Execution killed with signal 11
36 Runtime error 22 ms 4788 KB Execution killed with signal 11
37 Runtime error 20 ms 4116 KB Execution killed with signal 11
38 Runtime error 28 ms 5508 KB Execution killed with signal 11
39 Incorrect 2 ms 1356 KB Output isn't correct
40 Runtime error 6 ms 2892 KB Execution killed with signal 11
41 Runtime error 10 ms 3276 KB Execution killed with signal 11
42 Incorrect 9 ms 2096 KB Output isn't correct
43 Incorrect 15 ms 2452 KB Output isn't correct
44 Incorrect 26 ms 3268 KB Output isn't correct
45 Runtime error 14 ms 4352 KB Execution killed with signal 11
46 Runtime error 37 ms 6424 KB Execution killed with signal 11
47 Incorrect 30 ms 3712 KB Output isn't correct
48 Incorrect 27 ms 3780 KB Output isn't correct
49 Runtime error 41 ms 6524 KB Execution killed with signal 11
50 Incorrect 3 ms 1484 KB Output isn't correct