oj.uz

Submission #392589

# Submission time Handle Problem Language Result Execution time Memory
392589 2021-04-21T10:52:45 Z patrikpavic2 Marriage questions (IZhO14_marriage) C++17
76 / 100
 1500 ms 6716 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], m1[N];
 
bool dodaj(int x){
	if(bio[x] == cookie) return 0;
	bio[x] = cookie;
	while((int)m1[x].size() > 0 && (!un[m1[x].back()] || par[m1[x].back()] != -1)) 
		m1[x].pop_back();
	if((int)m1[x].size() > 0){
		int y = m1[x].back(); 
		par[x] = y; par[y] = x;
		m1[x].pop_back();
		return 1;
	}
	for(int i = poc[x];i < deg[x] && un[v[x][i]];i++){
		if(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());
		for(int x : v[i + n]) m1[x].PB(i + n);
	}
	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++;
				if(par[par[l - 1]] != -1){
					for(int x : v[par[l - 1]]) m1[x].PB(par[l - 1]);
				}
			}	
		}		
		while(r < n && sol < m){
			un[r] = 1; sol += dodaj(r); cookie++;
			if(par[r] == -1){
				for(int x : v[r]) m1[x].PB(r);
			}
			r++;
		}
		ans += (n + 1 - r) * (sol == m);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

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

Subtask #1
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 1 ms 1868 KB Output is correct
7 Incorrect 1 ms 1868 KB Output isn't correct
8 Correct 1 ms 1868 KB Output is correct
9 Correct 1 ms 1868 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1868 KB Output is correct
13 Correct 2 ms 1868 KB Output is correct
14 Incorrect 1 ms 1868 KB Output isn't correct
15 Incorrect 1 ms 1868 KB Output isn't correct
16 Correct 1 ms 1868 KB Output is correct
17 Correct 1 ms 1868 KB Output is correct
18 Correct 1 ms 1868 KB Output is correct
19 Incorrect 3 ms 1996 KB Output isn't correct
20 Incorrect 2 ms 1868 KB Output isn't correct
21 Correct 1 ms 1868 KB Output is correct
22 Correct 1 ms 1868 KB Output is correct
23 Correct 2 ms 1868 KB Output is correct
24 Correct 2 ms 1868 KB Output is correct
25 Incorrect 14 ms 2252 KB Output isn't correct
26 Incorrect 5 ms 1996 KB Output isn't correct
27 Correct 2 ms 1868 KB Output is correct
28 Correct 2 ms 1868 KB Output is correct
29 Correct 8 ms 2124 KB Output is correct
30 Correct 7 ms 2124 KB Output is correct
31 Incorrect 106 ms 2924 KB Output isn't correct
32 Incorrect 22 ms 2124 KB Output isn't correct
33 Correct 2 ms 1996 KB Output is correct
34 Correct 2 ms 1996 KB Output is correct
35 Correct 133 ms 3564 KB Output is correct
36 Correct 100 ms 3520 KB Output is correct
37 Incorrect 318 ms 3216 KB Output isn't correct
38 Correct 175 ms 4304 KB Output is correct
39 Correct 17 ms 2296 KB Output is correct
40 Correct 8 ms 2580 KB Output is correct
41 Correct 90 ms 2948 KB Output is correct
42 Correct 233 ms 3308 KB Output is correct
43 Correct 276 ms 3672 KB Output is correct
44 Correct 727 ms 4436 KB Output is correct
45 Correct 96 ms 3956 KB Output is correct
46 Execution timed out 1594 ms 6196 KB Time limit exceeded
47 Correct 1196 ms 5072 KB Output is correct
48 Correct 1192 ms 5144 KB Output is correct
49 Execution timed out 1596 ms 6716 KB Time limit exceeded
50 Correct 52 ms 2372 KB Output is correct