oj.uz

답안 #363503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363503 2021-02-06T09:54:52 Z nicolaalexandra 결혼 문제 (IZhO14_marriage) C++14
50 / 100
 1500 ms 1900 KB 
#include <bits/stdc++.h>
#define DIM 30010
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;

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 add (){

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

    } while (ok);

}

void delete_ (){

    if (!Right[st]) /// nodul asta nu face parte din cuplaj
        return;

    cnt--; /// ramane nodul din stanga necuplat
    int nod = Right[st];
    Left[nod] = Right[st] = 0;

    st++;
    cupleaza(nod);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    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++){
        /// adaug nodul asta
        add ();

        while (cnt == n && st < dr){
            delete_();
            if (cnt < n){
                st--;
                add(); /// il adaug la loc
                break;
            }
        }

        if (cnt == n)
            sol += st;
    }

    cout<<sol;

    return 0;
}

Subtask #1
50.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Execution timed out 1584 ms 1004 KB Time limit exceeded
3 Execution timed out 1578 ms 1004 KB Time limit exceeded
4 Execution timed out 1592 ms 1004 KB Time limit exceeded
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 1 ms 1004 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 1 ms 1004 KB Output is correct
11 Correct 1 ms 1004 KB Output is correct
12 Correct 1 ms 1004 KB Output is correct
13 Execution timed out 1596 ms 1004 KB Time limit exceeded
14 Correct 1 ms 1004 KB Output is correct
15 Correct 1 ms 1004 KB Output is correct
16 Execution timed out 1582 ms 1004 KB Time limit exceeded
17 Correct 1 ms 1004 KB Output is correct
18 Correct 1 ms 1004 KB Output is correct
19 Correct 6 ms 1004 KB Output is correct
20 Correct 2 ms 1148 KB Output is correct
21 Correct 1 ms 1004 KB Output is correct
22 Execution timed out 1591 ms 1004 KB Time limit exceeded
23 Correct 2 ms 1004 KB Output is correct
24 Correct 1 ms 1004 KB Output is correct
25 Correct 73 ms 1132 KB Output is correct
26 Execution timed out 1582 ms 1004 KB Time limit exceeded
27 Correct 2 ms 1004 KB Output is correct
28 Execution timed out 1591 ms 1004 KB Time limit exceeded
29 Execution timed out 1564 ms 1132 KB Time limit exceeded
30 Execution timed out 1584 ms 1132 KB Time limit exceeded
31 Correct 802 ms 1388 KB Output is correct
32 Execution timed out 1599 ms 1132 KB Time limit exceeded
33 Correct 6 ms 1004 KB Output is correct
34 Execution timed out 1588 ms 1132 KB Time limit exceeded
35 Correct 191 ms 1516 KB Output is correct
36 Correct 178 ms 1596 KB Output is correct
37 Execution timed out 1556 ms 1644 KB Time limit exceeded
38 Incorrect 331 ms 1772 KB Output isn't correct
39 Execution timed out 1595 ms 1260 KB Time limit exceeded
40 Correct 279 ms 1132 KB Output is correct
41 Execution timed out 1586 ms 1260 KB Time limit exceeded
42 Execution timed out 1587 ms 1356 KB Time limit exceeded
43 Execution timed out 1590 ms 1484 KB Time limit exceeded
44 Execution timed out 1590 ms 1900 KB Time limit exceeded
45 Execution timed out 1598 ms 1388 KB Time limit exceeded
46 Execution timed out 1574 ms 1900 KB Time limit exceeded
47 Execution timed out 1588 ms 1772 KB Time limit exceeded
48 Execution timed out 1576 ms 1648 KB Time limit exceeded
49 Execution timed out 1587 ms 1844 KB Time limit exceeded
50 Execution timed out 1590 ms 1388 KB Time limit exceeded