답안 #95448 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95448	2019-02-01T08:42:30 Z	choikiwon	결혼 문제 (IZhO14_marriage)	C++17	36 / 100	1500 ms	263168 KB

marriage

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MN = 100010;

int N, M, K;
vector<int> adj[MN], U, V;
int matched[MN], chk[MN], who[MN], vis[MN];

bool dfs(int u, int t, int lb, int ub) {
    if(t) {
        if(!chk[u]) {
            chk[u] = 1;
            return true;
        }

        int e = who[u];
        int v = U[e] + V[e] - u;

        if(dfs(v, 0, lb, ub)) {
            matched[e] = 0;
            return true;
        }
        else return false;
    }
    else {
        for(int i = 0; i < adj[u].size(); i++) {
            int e = adj[u][i];
            int v = U[e] + V[e] - u;
            if(v < N && (v < lb || ub < v)) continue;
            if(chk[v] && vis[v]) continue;
            if(!matched[e] && dfs(v, 1, lb, ub)) {
                who[u] = e;
                who[v] = e;
                matched[e] = 1;
                return true;
            }
        }
        return false;
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &K);

    for(int i = 0; i < K; i++) {
        int a, b; scanf("%d %d", &a, &b);
        a--; b--;

        adj[a].push_back(i);
        adj[b + N].push_back(i);
        U.push_back(a);
        V.push_back(b + N);
    }

    ll ans = 0;
    int matching = 0;
    int j = 0;
    for(int i = 0; i < N; i++) {
        while(j < N && matching < M) {
            for(int k = 0; k < M; k++) vis[N + k] = 0;
            if(dfs(j, 0, i, j)) {
                matching++;
                chk[j] = 1;
            }
            j++;
        }
        if(matching < M) break;
        ans += N - j + 1;

        if(chk[i]) {
            matching--;
            int v = U[ who[i] ] + V[ who[i] ] - i;
            chk[v] = 0;
            for(int k = 0; k < M; k++) if(chk[N + k]) {
                int e = who[N + k];
                int x = U[e] + V[e] - (N + k);
                vis[x] = 0;
            }
            if(dfs(v, 0, i + 1, j - 1)) {
                matching++;
                chk[v] = 1;
            }
        }
    }
    printf("%lld", ans);
}

Compilation message

marriage.cpp: In function 'bool dfs(int, int, int, int)':
marriage.cpp:29:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &M, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:49:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
36.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	205 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Runtime error	208 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Correct	4 ms	2680 KB	Output is correct
4	Correct	3 ms	2680 KB	Output is correct
5	Correct	3 ms	2680 KB	Output is correct
6	Correct	4 ms	2680 KB	Output is correct
7	Runtime error	226 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Correct	4 ms	2680 KB	Output is correct
9	Correct	4 ms	2680 KB	Output is correct
10	Runtime error	209 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Correct	3 ms	2680 KB	Output is correct
12	Correct	3 ms	2680 KB	Output is correct
13	Correct	3 ms	2680 KB	Output is correct
14	Runtime error	196 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	210 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Correct	3 ms	2680 KB	Output is correct
17	Runtime error	210 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	252 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	208 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	225 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
21	Correct	4 ms	2680 KB	Output is correct
22	Correct	4 ms	2680 KB	Output is correct
23	Execution timed out	1573 ms	2680 KB	Time limit exceeded
24	Execution timed out	1564 ms	2680 KB	Time limit exceeded
25	Runtime error	228 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
26	Runtime error	243 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
27	Correct	4 ms	2680 KB	Output is correct
28	Correct	4 ms	2680 KB	Output is correct
29	Execution timed out	1575 ms	2988 KB	Time limit exceeded
30	Execution timed out	1571 ms	3064 KB	Time limit exceeded
31	Runtime error	231 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
32	Runtime error	214 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
33	Correct	4 ms	2808 KB	Output is correct
34	Correct	6 ms	2808 KB	Output is correct
35	Execution timed out	1559 ms	4584 KB	Time limit exceeded
36	Execution timed out	1571 ms	4328 KB	Time limit exceeded
37	Runtime error	243 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
38	Execution timed out	1566 ms	4840 KB	Time limit exceeded
39	Correct	58 ms	3064 KB	Output is correct
40	Runtime error	215 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
41	Execution timed out	1582 ms	103848 KB	Time limit exceeded
42	Execution timed out	1565 ms	3448 KB	Time limit exceeded
43	Execution timed out	1577 ms	3824 KB	Time limit exceeded
44	Execution timed out	1576 ms	4580 KB	Time limit exceeded
45	Runtime error	340 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
46	Runtime error	301 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
47	Execution timed out	1554 ms	4936 KB	Time limit exceeded
48	Execution timed out	1558 ms	4812 KB	Time limit exceeded
49	Runtime error	284 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
50	Correct	83 ms	3064 KB	Output is correct

답안 #95448

Compilation message

Subtask #1 36.0 / 100.0

Subtask #1
36.0 / 100.0