oj.uz

답안 #363502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363502 2021-02-06T09:49:58 Z nicolaalexandra 결혼 문제 (IZhO14_marriage) C++14
50 / 100
 1500 ms 3116 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);
    }

    /*for (i=1;i<=n;i++){
        sort (L[i].begin(),L[i].end());
        reverse (L[i].begin(),L[i].end());
    }*/

    int sol = 0;
    st = 1;
    for (dr=1;dr<=m;dr++){
        /// adaug nodul asta
        add ();

        while (cnt == n && st <= i){
            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 1590 ms 1004 KB Time limit exceeded
3 Execution timed out 1585 ms 1004 KB Time limit exceeded
4 Execution timed out 1592 ms 1152 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 1581 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 7 ms 1004 KB Output is correct
20 Correct 2 ms 1004 KB Output is correct
21 Correct 1 ms 1004 KB Output is correct
22 Execution timed out 1579 ms 1004 KB Time limit exceeded
23 Correct 2 ms 1004 KB Output is correct
24 Correct 2 ms 1004 KB Output is correct
25 Correct 77 ms 1260 KB Output is correct
26 Execution timed out 1584 ms 1004 KB Time limit exceeded
27 Correct 2 ms 1004 KB Output is correct
28 Execution timed out 1577 ms 1004 KB Time limit exceeded
29 Execution timed out 1530 ms 1260 KB Time limit exceeded
30 Execution timed out 1594 ms 1132 KB Time limit exceeded
31 Correct 872 ms 1900 KB Output is correct
32 Execution timed out 1557 ms 1164 KB Time limit exceeded
33 Correct 6 ms 1004 KB Output is correct
34 Execution timed out 1573 ms 1132 KB Time limit exceeded
35 Correct 223 ms 2284 KB Output is correct
36 Correct 186 ms 2284 KB Output is correct
37 Execution timed out 1591 ms 1900 KB Time limit exceeded
38 Incorrect 418 ms 2536 KB Output isn't correct
39 Execution timed out 1582 ms 1260 KB Time limit exceeded
40 Correct 302 ms 1644 KB Output is correct
41 Execution timed out 1582 ms 1516 KB Time limit exceeded
42 Execution timed out 1584 ms 1516 KB Time limit exceeded
43 Execution timed out 1588 ms 2028 KB Time limit exceeded
44 Execution timed out 1563 ms 2796 KB Time limit exceeded
45 Execution timed out 1520 ms 1696 KB Time limit exceeded
46 Execution timed out 1582 ms 2924 KB Time limit exceeded
47 Execution timed out 1563 ms 3116 KB Time limit exceeded
48 Execution timed out 1577 ms 2868 KB Time limit exceeded
49 Execution timed out 1584 ms 2832 KB Time limit exceeded
50 Execution timed out 1584 ms 1388 KB Time limit exceeded