oj.uz

Submission #171978

# Submission time Handle Problem Language Result Execution time Memory
171978 2019-12-30T17:50:11 Z DeD_TihoN Marriage questions (IZhO14_marriage) C++14
72 / 100
 1500 ms 3192 KB 
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define ull unsigned long long
#define endl '\n'
#define y1 yaumru
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter vector<int>::iterator
#define int long long
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=30000+7;
const int inf=1e18+5;
const int mod=1e9+7;
const ld eps=1e-9;

vector<int>g[N];
bool used[N];
int mt[N];
int n,m;

bool try_kuhn (int v,int l,int r) {
	if (used[v])  return false;
	used[v] = true;
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (to<l || to>r)continue;
		if (mt[to] == -1 || try_kuhn (mt[to],l,r)) {
			mt[to] = v;
			return true;
		}
	}
	return false;
}

bool check(int l,int r)
{
    fill(mt,mt+n+1,-1);
    for (int i=1;i<=m;++i){
        fill(used,used+m+1,false);
        try_kuhn(i,l,r);
    }
    int ans=0;
    for (int i=1;i<=n;++i){
        if (mt[i]!=-1)++ans;
    }
    if (ans!=m)return false;
    return true;
}

main ()
{
    ios;
    int k;
    cin>>n>>m>>k;
    for (int i=1;i<=k;++i){
        int x,y;
        cin>>x>>y;
        swap(x,y);
        g[x].pb(y);
    }
    int ans=0;
    int r=1;
    for (int i=1;i<=n;++i){
        while(r<=n && !check(i,r))++r;
        ans+=n-r+1;
    }
    cout<<ans<<endl;
}

Compilation message

marriage.cpp:72:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^

Subtask #1
72.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 992 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1020 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 2 ms 1016 KB Output is correct
12 Correct 2 ms 1016 KB Output is correct
13 Correct 3 ms 1016 KB Output is correct
14 Correct 3 ms 1016 KB Output is correct
15 Correct 3 ms 1020 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 3 ms 1096 KB Output is correct
18 Correct 2 ms 1016 KB Output is correct
19 Correct 11 ms 1144 KB Output is correct
20 Correct 5 ms 1116 KB Output is correct
21 Correct 3 ms 1064 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 8 ms 1016 KB Output is correct
24 Correct 6 ms 1016 KB Output is correct
25 Correct 176 ms 1272 KB Output is correct
26 Correct 52 ms 1160 KB Output is correct
27 Correct 4 ms 1016 KB Output is correct
28 Correct 21 ms 1016 KB Output is correct
29 Correct 19 ms 1268 KB Output is correct
30 Correct 13 ms 1272 KB Output is correct
31 Execution timed out 1567 ms 1692 KB Time limit exceeded
32 Correct 815 ms 1404 KB Output is correct
33 Correct 10 ms 1144 KB Output is correct
34 Correct 706 ms 1244 KB Output is correct
35 Execution timed out 1568 ms 2808 KB Time limit exceeded
36 Execution timed out 1570 ms 2680 KB Time limit exceeded
37 Execution timed out 1575 ms 2040 KB Time limit exceeded
38 Execution timed out 1578 ms 2772 KB Time limit exceeded
39 Execution timed out 1576 ms 1408 KB Time limit exceeded
40 Correct 1494 ms 1400 KB Output is correct
41 Execution timed out 1565 ms 1656 KB Time limit exceeded
42 Correct 933 ms 1784 KB Output is correct
43 Correct 1076 ms 2268 KB Output is correct
44 Execution timed out 1568 ms 2680 KB Time limit exceeded
45 Execution timed out 1565 ms 2040 KB Time limit exceeded
46 Execution timed out 1578 ms 3064 KB Time limit exceeded
47 Execution timed out 1567 ms 2936 KB Time limit exceeded
48 Execution timed out 1558 ms 2936 KB Time limit exceeded
49 Execution timed out 1565 ms 3192 KB Time limit exceeded
50 Execution timed out 1568 ms 1528 KB Time limit exceeded