oj.uz

답안 #364428

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364428 2021-02-09T06:06:33 Z nicolaalexandra 결혼 문제 (IZhO14_marriage) C++14
14 / 100
 2 ms 3052 KB 
#include <bits/stdc++.h>
#define DIM 30010
#define DIMBUFF 7000000
using namespace std;

vector <int> L[DIM];
bitset <DIM> f;
int Left[DIM],Right[DIM];
int n,m,k,i,x,y,cnt,st,dr,pos;
char buff[DIMBUFF];

int cupleaza (int nod){
    if (f[nod])
        return 0;
    f[nod] = 1;
    for (auto vecin : L[nod]){
        if (!(vecin >= st && vecin <= dr))
            continue;

        if (!Right[vecin]){
            Right[vecin] = nod;
            Left[nod] = vecin;
            cnt++;
            return 1;
        }
    }

    for (auto vecin : L[nod]){
        if (!(vecin >= st && vecin <= dr))
            continue;

        if (cupleaza (Right[vecin])){
            Left[nod] = vecin;
            Right[vecin] = nod;
            return 1;
        }
    }

    return 0;
}


void cuplaj (){

    int ok = 0;
    do{
        f.reset();
        ok = 0;
        for (int i=1;i<=n;i++){
            if (!Left[i] && cupleaza (i))
                ok = 1;
        }

    } while (ok && cnt < n);

}


int get_nr (){

    while (!(buff[pos] >= '0' && buff[pos] <= '9'))
        pos++;

    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr * 10 + buff[pos] - '0';
        pos++;
    }

    return nr;

}

int main (){

    FILE *fin = stdin;
    FILE *fout = stdout;

    fread (buff,1,DIMBUFF,fin);

    cin>>m>>n>>k;
    for (i=1;i<=k;i++){
        cin>>x>>y;
        L[y].push_back(x);
    }

    int sol = 0;
    st = 1;
    for (dr=1;dr<=m;dr++){

        if (dr >= n)
            cuplaj();

        while (cnt == n && st < dr){

            if (Right[st]){
                cnt--; /// ramane nodul din stanga necuplat
                int nod = Right[st];
                Left[nod] = Right[st] = 0;
            }

            st++;

            cuplaj();
        }

        sol += st - 1;
    }

    cout<<sol;

    return 0;
}

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:77:11: warning: unused variable 'fout' [-Wunused-variable]
   77 |     FILE *fout = stdout;
      |           ^~~~
marriage.cpp:79:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   79 |     fread (buff,1,DIMBUFF,fin);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1004 KB Output isn't correct
2 Incorrect 1 ms 1004 KB Output isn't correct
3 Incorrect 1 ms 1004 KB Output isn't correct
4 Incorrect 1 ms 1004 KB Output isn't correct
5 Incorrect 1 ms 1004 KB Output isn't correct
6 Incorrect 1 ms 1004 KB Output isn't correct
7 Incorrect 1 ms 1004 KB Output isn't correct
8 Incorrect 1 ms 1004 KB Output isn't correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 1 ms 1004 KB Output is correct
11 Incorrect 1 ms 1004 KB Output isn't correct
12 Correct 1 ms 1004 KB Output is correct
13 Incorrect 1 ms 1004 KB Output isn't correct
14 Incorrect 1 ms 1036 KB Output isn't correct
15 Incorrect 1 ms 1004 KB Output isn't correct
16 Incorrect 1 ms 1004 KB Output isn't correct
17 Incorrect 1 ms 1004 KB Output isn't correct
18 Incorrect 1 ms 1004 KB Output isn't correct
19 Incorrect 1 ms 1004 KB Output isn't correct
20 Incorrect 1 ms 1004 KB Output isn't correct
21 Correct 1 ms 1004 KB Output is correct
22 Incorrect 1 ms 1152 KB Output isn't correct
23 Incorrect 1 ms 1004 KB Output isn't correct
24 Incorrect 1 ms 1004 KB Output isn't correct
25 Incorrect 1 ms 1132 KB Output isn't correct
26 Incorrect 1 ms 1004 KB Output isn't correct
27 Correct 1 ms 1004 KB Output is correct
28 Incorrect 1 ms 1004 KB Output isn't correct
29 Incorrect 1 ms 1132 KB Output isn't correct
30 Incorrect 1 ms 1132 KB Output isn't correct
31 Incorrect 1 ms 1772 KB Output isn't correct
32 Incorrect 1 ms 1132 KB Output isn't correct
33 Correct 1 ms 1004 KB Output is correct
34 Incorrect 1 ms 1004 KB Output isn't correct
35 Incorrect 2 ms 2540 KB Output isn't correct
36 Incorrect 2 ms 2284 KB Output isn't correct
37 Incorrect 1 ms 1900 KB Output isn't correct
38 Incorrect 2 ms 2668 KB Output isn't correct
39 Incorrect 1 ms 1152 KB Output isn't correct
40 Correct 1 ms 1260 KB Output is correct
41 Incorrect 1 ms 1388 KB Output isn't correct
42 Incorrect 1 ms 1516 KB Output isn't correct
43 Incorrect 2 ms 1900 KB Output isn't correct
44 Incorrect 2 ms 2668 KB Output isn't correct
45 Incorrect 1 ms 1644 KB Output isn't correct
46 Incorrect 2 ms 2816 KB Output isn't correct
47 Incorrect 2 ms 3052 KB Output isn't correct
48 Incorrect 2 ms 2796 KB Output isn't correct
49 Incorrect 2 ms 3052 KB Output isn't correct
50 Incorrect 1 ms 1132 KB Output isn't correct