oj.uz

Submission #171982

# Submission time Handle Problem Language Result Execution time Memory
171982 2019-12-30T18:01:58 Z DeD_TihoN Marriage questions (IZhO14_marriage) C++14
86 / 100
 1500 ms 2424 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 used1[N];
bool used2[N];

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;
			used2[v]=true;
			return true;
		}
	}
	return false;
}

bool check(int l,int r)
{
    fill(mt,mt+n+1,-1);
    fill(used1,used1+m+1,false);
    fill(used2,used2+m+1,false);
    for (int i=1;i<=m;++i){
        for (int j=0;j<g[i].size();++j){
            int to=g[i][j];
            if (to>=l && to<=r){
                if (mt[to]==-1){
                    mt[to]=i;
                    used1[i]=true;
                    used2[i]=true;
                    break;
                }
            }
        }
    }
    for (int i=1;i<=m;++i){
        if (used1[i])continue;
        fill(used,used+m+1,false);
        try_kuhn(i,l,r);
        if (!used2[i])return false;
    }
    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: In function 'bool check(long long int, long long int)':
marriage.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<g[i].size();++j){
                      ~^~~~~~~~~~~~
marriage.cpp: At global scope:
marriage.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^

Subtask #1
86.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 2 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 1016 KB Output is correct
10 Correct 2 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 3 ms 1144 KB Output is correct
14 Correct 3 ms 1020 KB Output is correct
15 Correct 3 ms 1016 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 3 ms 1016 KB Output is correct
18 Correct 3 ms 1144 KB Output is correct
19 Correct 5 ms 1144 KB Output is correct
20 Correct 4 ms 1144 KB Output is correct
21 Correct 3 ms 1016 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 3 ms 1016 KB Output is correct
24 Correct 3 ms 1016 KB Output is correct
25 Correct 61 ms 1272 KB Output is correct
26 Correct 26 ms 1144 KB Output is correct
27 Correct 3 ms 1020 KB Output is correct
28 Correct 4 ms 1144 KB Output is correct
29 Correct 7 ms 1144 KB Output is correct
30 Correct 7 ms 1144 KB Output is correct
31 Correct 515 ms 1784 KB Output is correct
32 Correct 14 ms 1144 KB Output is correct
33 Correct 4 ms 1144 KB Output is correct
34 Correct 10 ms 1144 KB Output is correct
35 Correct 162 ms 2180 KB Output is correct
36 Correct 135 ms 2168 KB Output is correct
37 Execution timed out 1568 ms 1656 KB Time limit exceeded
38 Correct 153 ms 2040 KB Output is correct
39 Correct 440 ms 1340 KB Output is correct
40 Correct 390 ms 1272 KB Output is correct
41 Correct 891 ms 1628 KB Output is correct
42 Correct 494 ms 1528 KB Output is correct
43 Correct 657 ms 1656 KB Output is correct
44 Correct 1236 ms 2296 KB Output is correct
45 Execution timed out 1558 ms 1788 KB Time limit exceeded
46 Execution timed out 1579 ms 2424 KB Time limit exceeded
47 Execution timed out 1571 ms 2296 KB Time limit exceeded
48 Execution timed out 1579 ms 2296 KB Time limit exceeded
49 Execution timed out 1579 ms 2424 KB Time limit exceeded
50 Execution timed out 1559 ms 1500 KB Time limit exceeded