답안 #800112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800112	2023-08-01T10:20:20 Z	SlavaKemDev	급행열차 20/19 (ROI19_express)	C++17	39 / 100	766 ms	704640 KB

express

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <random>
#include <cassert>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <thread>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpll = vector<pair<ll, ll>>;
using vii = vector<int>;

#define fill(a) for (ll i = 0; i < (a).size(); i++) cin >> (a)[i]
#define mp make_pair
#define mt make_tuple
#define bs(a, b) binary_search((a).begin(), (a).end(), (b))

ld EPS = 1e-9;
ld phi = (1 + sqrt(5)) / 2;

ll MOD = 1e9 + 7;
ll INF = 1e18;
ll P = 239;
ll B = 550;

struct Edge {
    ll to, w;
};

vector<vector<Edge>> g;
vector<bitset<10001>> c;
vector<ll> order;
vector<bool> used;

void dfs(ll v) {
    used[v] = true;
    for (Edge edge : g[v])
        if (!used[edge.to])
            dfs(edge.to);
    order.push_back(v);
}

int main() {
#ifdef LOCAL
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("err.txt", "w", stderr);

    clock_t timer = clock();
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(64);
    cout << fixed;
#endif

    ll t;
    cin >> t;

    while (t--) {
        ll n, m, q, p;
        cin >> n >> m >> q >> p;

        g.assign(n, {});
        used.assign(n, false);
        order.clear();

        for (ll i = 0; i < m; i++) {
            ll u, v, w;
            cin >> u >> v >> w;
            u--; v--;
            g[u].push_back({v, w});
        }

        dfs(0);
        reverse(order.begin(), order.end());

        c.assign(n, bitset<10001>());
        c[0][0] = true;
        vector<vector<ll>> cn(n);
        cn[0].push_back(0);


        for (ll v : order) {
            for (Edge edge : g[v])
                if (n <= 10 && m <= 10)
                    for (ll item : cn[v]) cn[edge.to].push_back(item + edge.w);
                else
                    c[edge.to] |= c[v] << edge.w;
        }

        while (q--) {
            ll f, r;
            cin >> f >> r;
            f--;

            bool ok = false;

            if (n <= 10 && m <= 10) {
                for (ll i : cn[f]) ok |= r <= i && i <= r * p / (p - 1);
            } else {
                for (ll i = r; i <= r * p / (p - 1); i++) ok |= c[f][i];
            }
            cout << ok;
        }

        cout  << "\n";
    }

#ifdef LOCAL
    cout << endl << "Execution time: " << (ld)(clock() - timer) / CLOCKS_PER_SEC;
#endif
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	320 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	4 ms	460 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	5 ms	660 KB	Output is correct
13	Correct	6 ms	596 KB	Output is correct
14	Correct	5 ms	588 KB	Output is correct
15	Correct	6 ms	596 KB	Output is correct
16	Correct	4 ms	596 KB	Output is correct
17	Correct	5 ms	596 KB	Output is correct
18	Correct	5 ms	596 KB	Output is correct
19	Correct	5 ms	596 KB	Output is correct
20	Correct	5 ms	596 KB	Output is correct
21	Correct	5 ms	572 KB	Output is correct
22	Correct	4 ms	468 KB	Output is correct
23	Correct	4 ms	468 KB	Output is correct
24	Correct	4 ms	340 KB	Output is correct
25	Correct	4 ms	460 KB	Output is correct
26	Correct	4 ms	452 KB	Output is correct
27	Correct	4 ms	460 KB	Output is correct
28	Correct	4 ms	340 KB	Output is correct
29	Correct	4 ms	464 KB	Output is correct
30	Correct	4 ms	468 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	316 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	4 ms	1108 KB	Output is correct
11	Correct	4 ms	1076 KB	Output is correct
12	Correct	6 ms	5716 KB	Output is correct
13	Correct	4 ms	1740 KB	Output is correct
14	Correct	4 ms	468 KB	Output is correct
15	Correct	3 ms	468 KB	Output is correct
16	Correct	4 ms	724 KB	Output is correct
17	Correct	4 ms	540 KB	Output is correct
18	Correct	5 ms	724 KB	Output is correct
19	Correct	5 ms	468 KB	Output is correct
20	Correct	5 ms	724 KB	Output is correct
21	Correct	5 ms	532 KB	Output is correct
22	Correct	6 ms	4052 KB	Output is correct
23	Correct	6 ms	3668 KB	Output is correct
24	Correct	6 ms	1364 KB	Output is correct
25	Correct	6 ms	1108 KB	Output is correct
26	Correct	7 ms	1308 KB	Output is correct
27	Correct	6 ms	1624 KB	Output is correct
28	Correct	5 ms	340 KB	Output is correct
29	Correct	3 ms	456 KB	Output is correct
30	Correct	2 ms	588 KB	Output is correct
31	Correct	2 ms	596 KB	Output is correct
32	Correct	2 ms	1748 KB	Output is correct

Subtask #3
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	766 ms	704640 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	766 ms	704640 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Runtime error	1 ms	724 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Runtime error	1 ms	724 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	320 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	4 ms	460 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	5 ms	660 KB	Output is correct
13	Correct	6 ms	596 KB	Output is correct
14	Correct	5 ms	588 KB	Output is correct
15	Correct	6 ms	596 KB	Output is correct
16	Correct	4 ms	596 KB	Output is correct
17	Correct	5 ms	596 KB	Output is correct
18	Correct	5 ms	596 KB	Output is correct
19	Correct	5 ms	596 KB	Output is correct
20	Correct	5 ms	596 KB	Output is correct
21	Correct	5 ms	572 KB	Output is correct
22	Correct	4 ms	468 KB	Output is correct
23	Correct	4 ms	468 KB	Output is correct
24	Correct	4 ms	340 KB	Output is correct
25	Correct	4 ms	460 KB	Output is correct
26	Correct	4 ms	452 KB	Output is correct
27	Correct	4 ms	460 KB	Output is correct
28	Correct	4 ms	340 KB	Output is correct
29	Correct	4 ms	464 KB	Output is correct
30	Correct	4 ms	468 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	0 ms	316 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	0 ms	212 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	0 ms	212 KB	Output is correct
40	Correct	4 ms	1108 KB	Output is correct
41	Correct	4 ms	1076 KB	Output is correct
42	Correct	6 ms	5716 KB	Output is correct
43	Correct	4 ms	1740 KB	Output is correct
44	Correct	4 ms	468 KB	Output is correct
45	Correct	3 ms	468 KB	Output is correct
46	Correct	4 ms	724 KB	Output is correct
47	Correct	4 ms	540 KB	Output is correct
48	Correct	5 ms	724 KB	Output is correct
49	Correct	5 ms	468 KB	Output is correct
50	Correct	5 ms	724 KB	Output is correct
51	Correct	5 ms	532 KB	Output is correct
52	Correct	6 ms	4052 KB	Output is correct
53	Correct	6 ms	3668 KB	Output is correct
54	Correct	6 ms	1364 KB	Output is correct
55	Correct	6 ms	1108 KB	Output is correct
56	Correct	7 ms	1308 KB	Output is correct
57	Correct	6 ms	1624 KB	Output is correct
58	Correct	5 ms	340 KB	Output is correct
59	Correct	3 ms	456 KB	Output is correct
60	Correct	2 ms	588 KB	Output is correct
61	Correct	2 ms	596 KB	Output is correct
62	Correct	2 ms	1748 KB	Output is correct
63	Correct	0 ms	212 KB	Output is correct
64	Runtime error	766 ms	704640 KB	Execution killed with signal 11
65	Halted	0 ms	0 KB	-

답안 #800112

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 24.0 / 24.0

Subtask #3 0 / 17.0

Subtask #4 0 / 11.0

Subtask #5 0 / 11.0

Subtask #6 0 / 11.0

Subtask #7 0 / 11.0

Subtask #1
15.0 / 15.0

Subtask #2
24.0 / 24.0

Subtask #3
0 / 17.0

Subtask #4
0 / 11.0

Subtask #5
0 / 11.0

Subtask #6
0 / 11.0

Subtask #7
0 / 11.0