oj.uz

Submission #171981

# Submission time Handle Problem Language Result Execution time Memory
171981 2019-12-30T17:53:59 Z DeD_TihoN Marriage questions (IZhO14_marriage) C++14
80 / 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 used1[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;
			return true;
		}
	}
	return false;
}

bool check(int l,int r)
{
    fill(mt,mt+n+1,-1);
    fill(used1,used1+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;
                    break;
                }
            }
        }
    }
    for (int i=1;i<=m;++i){
        if (used1[i])continue;
        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: In function 'bool check(long long int, long long int)':
marriage.cpp:63: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:87:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^

Subtask #1
80.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 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 2 ms 1096 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 2 ms 1016 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 1144 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 1016 KB Output is correct
19 Correct 9 ms 1144 KB Output is correct
20 Correct 5 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 124 ms 1356 KB Output is correct
26 Correct 36 ms 1172 KB Output is correct
27 Correct 4 ms 1148 KB Output is correct
28 Correct 4 ms 1144 KB Output is correct
29 Correct 10 ms 1272 KB Output is correct
30 Correct 9 ms 1272 KB Output is correct
31 Execution timed out 1554 ms 1668 KB Time limit exceeded
32 Correct 1020 ms 1368 KB Output is correct
33 Correct 10 ms 1016 KB Output is correct
34 Correct 15 ms 1144 KB Output is correct
35 Correct 196 ms 3020 KB Output is correct
36 Correct 159 ms 2936 KB Output is correct
37 Execution timed out 1562 ms 2040 KB Time limit exceeded
38 Correct 255 ms 2984 KB Output is correct
39 Correct 843 ms 1500 KB Output is correct
40 Correct 1104 ms 1532 KB Output is correct
41 Execution timed out 1559 ms 1656 KB Time limit exceeded
42 Correct 1251 ms 1784 KB Output is correct
43 Correct 1476 ms 2268 KB Output is correct
44 Execution timed out 1558 ms 3064 KB Time limit exceeded
45 Execution timed out 1560 ms 2040 KB Time limit exceeded
46 Execution timed out 1561 ms 2936 KB Time limit exceeded
47 Execution timed out 1553 ms 3192 KB Time limit exceeded
48 Execution timed out 1553 ms 3064 KB Time limit exceeded
49 Execution timed out 1540 ms 3192 KB Time limit exceeded
50 Execution timed out 1557 ms 1400 KB Time limit exceeded