oj.uz

Submission #341258

# Submission time Handle Problem Language Result Execution time Memory
341258 2020-12-29T10:16:54 Z juggernaut Marriage questions (IZhO14_marriage) C++14
0 / 100
 1 ms 492 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,qq,mt[30005],GL,GR,vis[2005],timer;
vector<int>g[2005];
queue<int>q;
bool kuhn(int v){
    if(vis[v]==timer)return false;
    vis[v]=timer;
    for(int to:g[v]){
        if(to<GL||to>GR)continue;
        if(!mt[to]||kuhn(mt[to])){
            mt[to]=v;
            return true;
        }
    }
    return false;
}
bool check(){
    while(!q.empty()){
        int v=q.front();
        q.pop();
        timer++;
        if(!kuhn(v)){
            q.push(v);
            return false;
        }
    }
    return true;
}
int main(){vector<int>v={1,2,3,4,5,6,7,8,9};
    srand(time(NULL));
    vector<int>v1=v;
    random_shuffle(v.begin(),v.end());
    for(int i=0;i<9;i++)if(v[i]!=v1[i]){
        puts("SHUFFLE WORKS");
        return 0;
    }
    scanf("%d%d%d",&n,&m,&qq);
    while(qq--){
        int x,y;
        scanf("%d%d",&x,&y);
        g[y].push_back(x);
    }
    for(int i=1;i<=m;i++)q.push(i);
    int ans=0;
    GR=1;
    for(GL=1;GL<=n;GL++){
        while(GR<=n&&!check())GR++;
        ans+=n-GR+1;
        if(mt[GL]){
            q.push(mt[GL]);
            mt[GL]=0;
        }
    }
    cout<<ans;
}

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d%d%d",&n,&m,&qq);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
marriage.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 0 ms 364 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Incorrect 1 ms 364 KB Output isn't correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Incorrect 1 ms 364 KB Output isn't correct
11 Incorrect 1 ms 364 KB Output isn't correct
12 Incorrect 1 ms 364 KB Output isn't correct
13 Incorrect 1 ms 364 KB Output isn't correct
14 Incorrect 1 ms 364 KB Output isn't correct
15 Incorrect 1 ms 364 KB Output isn't correct
16 Incorrect 1 ms 364 KB Output isn't correct
17 Incorrect 1 ms 364 KB Output isn't correct
18 Incorrect 1 ms 364 KB Output isn't correct
19 Incorrect 1 ms 364 KB Output isn't correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Incorrect 1 ms 364 KB Output isn't correct
22 Incorrect 1 ms 364 KB Output isn't correct
23 Incorrect 1 ms 364 KB Output isn't correct
24 Incorrect 1 ms 364 KB Output isn't correct
25 Incorrect 1 ms 364 KB Output isn't correct
26 Incorrect 1 ms 364 KB Output isn't correct
27 Incorrect 1 ms 364 KB Output isn't correct
28 Incorrect 1 ms 364 KB Output isn't correct
29 Incorrect 1 ms 364 KB Output isn't correct
30 Incorrect 1 ms 364 KB Output isn't correct
31 Incorrect 1 ms 364 KB Output isn't correct
32 Incorrect 1 ms 400 KB Output isn't correct
33 Incorrect 1 ms 364 KB Output isn't correct
34 Incorrect 1 ms 364 KB Output isn't correct
35 Incorrect 1 ms 364 KB Output isn't correct
36 Incorrect 1 ms 364 KB Output isn't correct
37 Incorrect 1 ms 364 KB Output isn't correct
38 Incorrect 1 ms 364 KB Output isn't correct
39 Incorrect 1 ms 364 KB Output isn't correct
40 Incorrect 1 ms 364 KB Output isn't correct
41 Incorrect 1 ms 364 KB Output isn't correct
42 Incorrect 1 ms 364 KB Output isn't correct
43 Incorrect 1 ms 364 KB Output isn't correct
44 Incorrect 1 ms 364 KB Output isn't correct
45 Incorrect 1 ms 364 KB Output isn't correct
46 Incorrect 1 ms 492 KB Output isn't correct
47 Incorrect 1 ms 364 KB Output isn't correct
48 Incorrect 1 ms 364 KB Output isn't correct
49 Incorrect 1 ms 364 KB Output isn't correct
50 Incorrect 1 ms 364 KB Output isn't correct