답안 #93421 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93421	2019-01-08T10:56:45 Z	inom	결혼 문제 (IZhO14_marriage)	C++14	36 / 100	1500 ms	2936 KB

marriage

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define int long long
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
 
using namespace std;

const int N = 30030;
 
int TN = 1;

int n, m, k;
int cnt, ans;
int us[N][55];
bool flag = false;
vector<int> verr[N];

void rec(int a, int b, int cnt, int pos) {
    if (a > b) {
        if (cnt >= m) {
            flag = true; return;
        } else {
            return;
        }
    }
    if (cnt >= m) {
        flag = true; return;
    }
    for (int i: verr[a]) {
        if (!us[pos][i]) {
            us[pos][i] = 1;
            rec(a + 1, b, cnt + 1, pos);
            us[pos][i] = 0;
        }
    }
    rec(a + 1, b, cnt, pos);
}

void solve() {
    scanf("%lld %lld %lld", &n, &m, &k);
    for (int i = 1; i <= k; i++) {
        int x, y; 
        scanf("%lld %lld", &x, &y); verr[x].push_back(y);
    }
    int pos = 0;
    for (int i = 1; i <= n; i++) {
        int l = i, r = n;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (mid - i + 1 < m) {
                l = mid + 1; continue;
            }
            flag = false; cnt = 0; pos++;
            rec(i, mid, cnt, pos);
            if (flag) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        
        flag = false; cnt = 0; pos++;
        rec(i, r, cnt, pos);
        if (!flag) {
            continue;
        }
        flag = false; cnt = 0; pos++;
        rec(i, l, cnt, pos);
        if (flag) {
            ans += (n - l + 1);
        } else {
            ans += (n - r + 1);
        }
        // cout << i << " " << l << " " << r << "\n";
        /*for (int r = l + m - 1; r <= n; r++) {
            flag = false; cnt = 0;
            rec(l, r, cnt, ans + 1); ans += flag;
            if (flag) {
                ans += (n - r); break;
            }
        }*/
    }
    printf("%lld\n", ans);
    return;
}

signed main() {
    // in; out; // cin >> TN;
    while (TN--) { solve(); }
    return 0;
}

Compilation message

marriage.cpp: In function 'void solve()':
marriage.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &x, &y); verr[x].push_back(y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
36.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1016 KB	Output is correct
2	Correct	2 ms	1016 KB	Output is correct
3	Correct	2 ms	1016 KB	Output is correct
4	Correct	2 ms	1020 KB	Output is correct
5	Correct	2 ms	1016 KB	Output is correct
6	Correct	2 ms	1016 KB	Output is correct
7	Correct	1258 ms	1144 KB	Output is correct
8	Correct	2 ms	1016 KB	Output is correct
9	Correct	2 ms	1016 KB	Output is correct
10	Correct	2 ms	1016 KB	Output is correct
11	Correct	2 ms	1016 KB	Output is correct
12	Correct	2 ms	1020 KB	Output is correct
13	Correct	2 ms	1016 KB	Output is correct
14	Correct	229 ms	1016 KB	Output is correct
15	Correct	32 ms	1084 KB	Output is correct
16	Correct	4 ms	1016 KB	Output is correct
17	Correct	32 ms	1016 KB	Output is correct
18	Correct	7 ms	1016 KB	Output is correct
19	Execution timed out	1577 ms	1016 KB	Time limit exceeded
20	Execution timed out	1572 ms	1016 KB	Time limit exceeded
21	Execution timed out	1577 ms	1016 KB	Time limit exceeded
22	Execution timed out	1572 ms	1016 KB	Time limit exceeded
23	Execution timed out	1559 ms	1016 KB	Time limit exceeded
24	Execution timed out	1566 ms	1016 KB	Time limit exceeded
25	Execution timed out	1571 ms	1272 KB	Time limit exceeded
26	Execution timed out	1579 ms	1016 KB	Time limit exceeded
27	Execution timed out	1558 ms	1016 KB	Time limit exceeded
28	Execution timed out	1575 ms	1016 KB	Time limit exceeded
29	Execution timed out	1567 ms	1144 KB	Time limit exceeded
30	Execution timed out	1584 ms	1144 KB	Time limit exceeded
31	Execution timed out	1577 ms	1784 KB	Time limit exceeded
32	Execution timed out	1580 ms	1244 KB	Time limit exceeded
33	Execution timed out	1573 ms	1016 KB	Time limit exceeded
34	Execution timed out	1571 ms	1016 KB	Time limit exceeded
35	Execution timed out	1571 ms	2168 KB	Time limit exceeded
36	Execution timed out	1566 ms	2168 KB	Time limit exceeded
37	Execution timed out	1572 ms	1912 KB	Time limit exceeded
38	Execution timed out	1577 ms	2684 KB	Time limit exceeded
39	Execution timed out	1554 ms	1272 KB	Time limit exceeded
40	Execution timed out	1583 ms	1528 KB	Time limit exceeded
41	Execution timed out	1581 ms	1660 KB	Time limit exceeded
42	Execution timed out	1562 ms	1656 KB	Time limit exceeded
43	Execution timed out	1568 ms	1784 KB	Time limit exceeded
44	Execution timed out	1567 ms	2296 KB	Time limit exceeded
45	Execution timed out	1551 ms	1912 KB	Time limit exceeded
46	Execution timed out	1537 ms	2808 KB	Time limit exceeded
47	Execution timed out	1565 ms	2552 KB	Time limit exceeded
48	Execution timed out	1566 ms	2680 KB	Time limit exceeded
49	Execution timed out	1570 ms	2936 KB	Time limit exceeded
50	Execution timed out	1576 ms	1144 KB	Time limit exceeded

답안 #93421

Compilation message

Subtask #1 36.0 / 100.0

Subtask #1
36.0 / 100.0