oj.uz

Submission #39057

# Submission time Handle Problem Language Result Execution time Memory
39057 2018-01-09T06:41:08 Z Scayre Marriage questions (IZhO14_marriage) C++14
28 / 100
 1500 ms 3944 KB 
//
// omae wa mou shindeiru.
//

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define ll long long
#define ull unsigned ll
#define ioi exit(0);

#define f first
#define s second

#define inf (int)1e9 + 7

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define mp make_pair

#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)

#define pb push_back
#define ppb pop_back

#define endl "\n"

#define in(x) insert(x)

#define sz(x) (int)x.size()

#define all(x) x.begin(),x.end()

#define pw2(x) (1<<x) //2^x

#define sqr(x) ((x) * 1ll * (x))

using namespace std;

const int N = (int)3e4 + 7, MOD = (int)1e9 + 7;

int n,k,m;

vector <int> a[N];

map <int,vector<int> > mpp;

ll ans,res;

set <int> s;

void calc(int pos,int cnt){
	if(s.size()==m){
		ans=max(ans,(ll)n-(pos-1)+1);
		return;
	}
	if(pos>n){
		return;
	}
	for(int i=0;i<a[pos].size();i++){
		s.insert(a[pos][i]);
		mpp[a[pos][i]].pb(cnt);
		calc(pos+1,cnt+1);
		for(auto it=s.begin();it!=s.end();it++){
			int z=*it;
			while(mpp[z][mpp[z].size()-1]>=cnt){
				mpp[z].ppb();
			}
			if(mpp[z].size()==0)s.erase(z);
		}
	}
}

int main(){

	#ifdef IOI2019
		freopen ("in.txt", "r", stdin);
	#endif

	NFS

	cin >> n >> m >> k;

	for(int i=1;i<=k;i++){
		int x,y;
		cin >> x >> y;
		a[x].pb(y);
	}

	for(int i=1;i<=n;i++){
		ans=0;
		calc(i,1);
		res+=ans;
		if(ans==0){
			break;
		}
		s.clear();
		mpp.clear();
	}

	cout << res << endl;


	#ifdef IOI2019
		cout << "\nTime Elapsed : " << clock () * 1.0 / CLOCKS_PER_SEC << endl;
	#endif

	ioi
}

Compilation message

marriage.cpp: In function 'void calc(int, int)':
marriage.cpp:78:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(s.size()==m){
             ^
marriage.cpp:85:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[pos].size();i++){
               ^

Subtask #1
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2888 KB Output is correct
2 Incorrect 0 ms 2888 KB Output isn't correct
3 Incorrect 0 ms 2888 KB Output isn't correct
4 Incorrect 0 ms 2888 KB Output isn't correct
5 Correct 0 ms 2888 KB Output is correct
6 Correct 0 ms 2888 KB Output is correct
7 Execution timed out 1500 ms 2888 KB Execution timed out
8 Correct 0 ms 2888 KB Output is correct
9 Correct 0 ms 2888 KB Output is correct
10 Correct 0 ms 2888 KB Output is correct
11 Correct 0 ms 2888 KB Output is correct
12 Correct 0 ms 2888 KB Output is correct
13 Incorrect 0 ms 2888 KB Output isn't correct
14 Execution timed out 1500 ms 2888 KB Execution timed out
15 Execution timed out 1500 ms 2888 KB Execution timed out
16 Incorrect 0 ms 2888 KB Output isn't correct
17 Correct 1133 ms 2888 KB Output is correct
18 Correct 49 ms 2888 KB Output is correct
19 Execution timed out 1500 ms 2888 KB Execution timed out
20 Execution timed out 1500 ms 2888 KB Execution timed out
21 Correct 0 ms 2888 KB Output is correct
22 Incorrect 0 ms 2888 KB Output isn't correct
23 Execution timed out 1500 ms 2888 KB Execution timed out
24 Execution timed out 1500 ms 2888 KB Execution timed out
25 Execution timed out 1500 ms 2888 KB Execution timed out
26 Execution timed out 1500 ms 2888 KB Execution timed out
27 Correct 0 ms 2888 KB Output is correct
28 Incorrect 0 ms 2888 KB Output isn't correct
29 Incorrect 0 ms 2888 KB Output isn't correct
30 Incorrect 3 ms 2888 KB Output isn't correct
31 Execution timed out 1500 ms 3168 KB Execution timed out
32 Execution timed out 1500 ms 2888 KB Execution timed out
33 Correct 0 ms 2888 KB Output is correct
34 Incorrect 0 ms 2888 KB Output isn't correct
35 Execution timed out 1500 ms 3416 KB Execution timed out
36 Execution timed out 1500 ms 3416 KB Execution timed out
37 Execution timed out 1500 ms 3512 KB Execution timed out
38 Execution timed out 1500 ms 3912 KB Execution timed out
39 Incorrect 0 ms 2888 KB Output isn't correct
40 Correct 0 ms 3020 KB Output is correct
41 Incorrect 43 ms 3152 KB Output isn't correct
42 Incorrect 3 ms 3284 KB Output isn't correct
43 Incorrect 9 ms 3284 KB Output isn't correct
44 Incorrect 16 ms 3416 KB Output isn't correct
45 Incorrect 13 ms 3416 KB Output isn't correct
46 Execution timed out 1500 ms 3944 KB Execution timed out
47 Incorrect 23 ms 3680 KB Output isn't correct
48 Incorrect 16 ms 3680 KB Output isn't correct
49 Execution timed out 1500 ms 3944 KB Execution timed out
50 Incorrect 0 ms 2888 KB Output isn't correct