oj.uz

Submission #292688

# Submission time Handle Problem Language Result Execution time Memory
292688 2020-09-07T11:49:27 Z 최은수(#5797) Express 20/19 (ROI19_express) C++17
67 / 100
 5000 ms 876284 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
inline void merge(vector<ll>&v,const vector<ll>&vi,ll w,int p)
{
    int n=v.size(),m=vi.size();
    int i=0,j=0;
    vector<ll>nv;
    while(i<n&&j<m)
    {
        if(v[i]<vi[j]+w)
            nv.eb(v[i]),i++;
        else
            nv.eb(vi[j]+w),j++;
    }
    while(i<n||j<m)
    {
        if(i<n)
            nv.eb(v[i]),i++;
        else
            nv.eb(vi[j]+w),j++;
    }
    v.clear();
    for(ll&t:nv)
    {
        if((int)v.size()>1&&t*(p-1)<=v[(int)v.size()-2]*p)
            v.pop_back();
        v.eb(t);
    }
    return;
}
inline void solve()
{
    int n,m,q,p;
    cin>>n>>m>>q>>p;
    vector<vector<ll> >vv(n+1);
    vector<vector<pl> >adj(n+1);
    for(int i=0;i<m;i++)
    {
        int u,v;
        ll d;
        cin>>u>>v>>d;
        adj[v].eb(u,d);
    }
    vv[1].eb(0);
    for(int i=1;i++<n;)
        for(pl&t:adj[i])
            merge(vv[i],vv[t.fi],t.se,p);
    for(int qi=0;qi++<q;)
    {
        int i;
        ll r;
        cin>>i>>r;
        auto it=lower_bound(all(vv[i]),r);
        if(it!=vv[i].end()&&*it*(p-1)<=r*p)
            cout<<1;
        else
            cout<<0;
    }
    cout<<'\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t-->0)
        solve();
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 8 ms 384 KB Output is correct
13 Correct 10 ms 384 KB Output is correct
14 Correct 10 ms 384 KB Output is correct
15 Correct 8 ms 384 KB Output is correct
16 Correct 8 ms 384 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 10 ms 512 KB Output is correct
19 Correct 7 ms 384 KB Output is correct
20 Correct 9 ms 384 KB Output is correct
21 Correct 8 ms 384 KB Output is correct
22 Correct 9 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 7 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 6 ms 384 KB Output is correct
29 Correct 9 ms 384 KB Output is correct
30 Correct 8 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 17 ms 896 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 9 ms 768 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 768 KB Output is correct
23 Correct 6 ms 800 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 4 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 3 ms 384 KB Output is correct
32 Correct 25 ms 2432 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 501 ms 34504 KB Output is correct
3 Correct 399 ms 7644 KB Output is correct
4 Correct 380 ms 3896 KB Output is correct
5 Correct 333 ms 1144 KB Output is correct
6 Correct 392 ms 11388 KB Output is correct
7 Correct 392 ms 6360 KB Output is correct
8 Correct 408 ms 11996 KB Output is correct
9 Correct 365 ms 6136 KB Output is correct
10 Correct 361 ms 11484 KB Output is correct
11 Correct 327 ms 6020 KB Output is correct
12 Correct 112 ms 512 KB Output is correct
13 Correct 7 ms 384 KB Output is correct
14 Correct 8 ms 384 KB Output is correct
15 Correct 11 ms 384 KB Output is correct
16 Correct 11 ms 384 KB Output is correct
17 Correct 27 ms 384 KB Output is correct
18 Correct 137 ms 1036 KB Output is correct
19 Correct 21 ms 384 KB Output is correct
20 Correct 43 ms 384 KB Output is correct
21 Correct 43 ms 504 KB Output is correct
22 Correct 43 ms 424 KB Output is correct
23 Correct 340 ms 36344 KB Output is correct
24 Correct 1008 ms 144356 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 501 ms 34504 KB Output is correct
3 Correct 399 ms 7644 KB Output is correct
4 Correct 380 ms 3896 KB Output is correct
5 Correct 333 ms 1144 KB Output is correct
6 Correct 392 ms 11388 KB Output is correct
7 Correct 392 ms 6360 KB Output is correct
8 Correct 408 ms 11996 KB Output is correct
9 Correct 365 ms 6136 KB Output is correct
10 Correct 361 ms 11484 KB Output is correct
11 Correct 327 ms 6020 KB Output is correct
12 Correct 112 ms 512 KB Output is correct
13 Correct 7 ms 384 KB Output is correct
14 Correct 8 ms 384 KB Output is correct
15 Correct 11 ms 384 KB Output is correct
16 Correct 11 ms 384 KB Output is correct
17 Correct 27 ms 384 KB Output is correct
18 Correct 137 ms 1036 KB Output is correct
19 Correct 21 ms 384 KB Output is correct
20 Correct 43 ms 384 KB Output is correct
21 Correct 43 ms 504 KB Output is correct
22 Correct 43 ms 424 KB Output is correct
23 Correct 340 ms 36344 KB Output is correct
24 Correct 1008 ms 144356 KB Output is correct
25 Correct 651 ms 37580 KB Output is correct
26 Correct 815 ms 13232 KB Output is correct
27 Correct 790 ms 7008 KB Output is correct
28 Correct 761 ms 2540 KB Output is correct
29 Correct 603 ms 1144 KB Output is correct
30 Correct 636 ms 1524 KB Output is correct
31 Correct 668 ms 20484 KB Output is correct
32 Correct 604 ms 10356 KB Output is correct
33 Correct 507 ms 15036 KB Output is correct
34 Correct 458 ms 7676 KB Output is correct
35 Correct 636 ms 20088 KB Output is correct
36 Correct 605 ms 10336 KB Output is correct
37 Correct 203 ms 632 KB Output is correct
38 Correct 14 ms 384 KB Output is correct
39 Correct 13 ms 832 KB Output is correct
40 Execution timed out 5078 ms 848284 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 6 ms 1408 KB Output is correct
9 Correct 3 ms 416 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 5 ms 552 KB Output is correct
18 Correct 6 ms 1024 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 5 ms 896 KB Output is correct
21 Correct 7 ms 1280 KB Output is correct
22 Correct 4 ms 768 KB Output is correct
23 Correct 5 ms 896 KB Output is correct
24 Correct 5 ms 768 KB Output is correct
25 Correct 8 ms 1280 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 4 ms 384 KB Output is correct
37 Correct 4 ms 384 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 4 ms 384 KB Output is correct
40 Correct 4 ms 384 KB Output is correct
41 Correct 4 ms 384 KB Output is correct
42 Correct 4 ms 384 KB Output is correct
43 Correct 14 ms 2432 KB Output is correct
44 Correct 14 ms 2432 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 6 ms 1408 KB Output is correct
9 Correct 3 ms 416 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 5 ms 552 KB Output is correct
18 Correct 6 ms 1024 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 5 ms 896 KB Output is correct
21 Correct 7 ms 1280 KB Output is correct
22 Correct 4 ms 768 KB Output is correct
23 Correct 5 ms 896 KB Output is correct
24 Correct 5 ms 768 KB Output is correct
25 Correct 8 ms 1280 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 4 ms 384 KB Output is correct
37 Correct 4 ms 384 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 4 ms 384 KB Output is correct
40 Correct 4 ms 384 KB Output is correct
41 Correct 4 ms 384 KB Output is correct
42 Correct 4 ms 384 KB Output is correct
43 Correct 14 ms 2432 KB Output is correct
44 Correct 14 ms 2432 KB Output is correct
45 Correct 710 ms 9908 KB Output is correct
46 Correct 1721 ms 46176 KB Output is correct
47 Correct 820 ms 48248 KB Output is correct
48 Correct 658 ms 1460 KB Output is correct
49 Correct 490 ms 1652 KB Output is correct
50 Correct 503 ms 968 KB Output is correct
51 Correct 2 ms 384 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 37 ms 384 KB Output is correct
54 Correct 15 ms 384 KB Output is correct
55 Correct 399 ms 1360 KB Output is correct
56 Correct 1344 ms 1984 KB Output is correct
57 Correct 791 ms 1312 KB Output is correct
58 Correct 519 ms 1392 KB Output is correct
59 Correct 1271 ms 1864 KB Output is correct
60 Correct 428 ms 2624 KB Output is correct
61 Correct 1182 ms 21596 KB Output is correct
62 Correct 3450 ms 13212 KB Output is correct
63 Correct 1829 ms 10064 KB Output is correct
64 Correct 997 ms 1096 KB Output is correct
65 Correct 2313 ms 223736 KB Output is correct
66 Correct 561 ms 38904 KB Output is correct
67 Correct 705 ms 49628 KB Output is correct
68 Correct 597 ms 55800 KB Output is correct
69 Correct 1548 ms 240156 KB Output is correct
70 Correct 862 ms 78712 KB Output is correct
71 Correct 2565 ms 526088 KB Output is correct
72 Correct 295 ms 632 KB Output is correct
73 Correct 594 ms 55800 KB Output is correct
74 Correct 1336 ms 31940 KB Output is correct
75 Correct 124 ms 780 KB Output is correct
76 Correct 143 ms 1124 KB Output is correct
77 Correct 124 ms 776 KB Output is correct
78 Correct 268 ms 1076 KB Output is correct
79 Correct 514 ms 18852 KB Output is correct
80 Correct 509 ms 18940 KB Output is correct
81 Correct 515 ms 18964 KB Output is correct
82 Correct 524 ms 18852 KB Output is correct
83 Execution timed out 5122 ms 876284 KB Time limit exceeded
84 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 8 ms 384 KB Output is correct
13 Correct 10 ms 384 KB Output is correct
14 Correct 10 ms 384 KB Output is correct
15 Correct 8 ms 384 KB Output is correct
16 Correct 8 ms 384 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 10 ms 512 KB Output is correct
19 Correct 7 ms 384 KB Output is correct
20 Correct 9 ms 384 KB Output is correct
21 Correct 8 ms 384 KB Output is correct
22 Correct 9 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 7 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 6 ms 384 KB Output is correct
29 Correct 9 ms 384 KB Output is correct
30 Correct 8 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 0 ms 384 KB Output is correct
34 Correct 0 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 0 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 0 ms 384 KB Output is correct
39 Correct 0 ms 384 KB Output is correct
40 Correct 5 ms 384 KB Output is correct
41 Correct 17 ms 896 KB Output is correct
42 Correct 6 ms 768 KB Output is correct
43 Correct 9 ms 768 KB Output is correct
44 Correct 6 ms 384 KB Output is correct
45 Correct 3 ms 384 KB Output is correct
46 Correct 4 ms 384 KB Output is correct
47 Correct 6 ms 384 KB Output is correct
48 Correct 4 ms 384 KB Output is correct
49 Correct 6 ms 384 KB Output is correct
50 Correct 4 ms 384 KB Output is correct
51 Correct 5 ms 384 KB Output is correct
52 Correct 5 ms 768 KB Output is correct
53 Correct 6 ms 800 KB Output is correct
54 Correct 4 ms 384 KB Output is correct
55 Correct 4 ms 384 KB Output is correct
56 Correct 6 ms 384 KB Output is correct
57 Correct 5 ms 384 KB Output is correct
58 Correct 2 ms 384 KB Output is correct
59 Correct 3 ms 384 KB Output is correct
60 Correct 3 ms 384 KB Output is correct
61 Correct 3 ms 384 KB Output is correct
62 Correct 25 ms 2432 KB Output is correct
63 Correct 0 ms 384 KB Output is correct
64 Correct 501 ms 34504 KB Output is correct
65 Correct 399 ms 7644 KB Output is correct
66 Correct 380 ms 3896 KB Output is correct
67 Correct 333 ms 1144 KB Output is correct
68 Correct 392 ms 11388 KB Output is correct
69 Correct 392 ms 6360 KB Output is correct
70 Correct 408 ms 11996 KB Output is correct
71 Correct 365 ms 6136 KB Output is correct
72 Correct 361 ms 11484 KB Output is correct
73 Correct 327 ms 6020 KB Output is correct
74 Correct 112 ms 512 KB Output is correct
75 Correct 7 ms 384 KB Output is correct
76 Correct 8 ms 384 KB Output is correct
77 Correct 11 ms 384 KB Output is correct
78 Correct 11 ms 384 KB Output is correct
79 Correct 27 ms 384 KB Output is correct
80 Correct 137 ms 1036 KB Output is correct
81 Correct 21 ms 384 KB Output is correct
82 Correct 43 ms 384 KB Output is correct
83 Correct 43 ms 504 KB Output is correct
84 Correct 43 ms 424 KB Output is correct
85 Correct 340 ms 36344 KB Output is correct
86 Correct 1008 ms 144356 KB Output is correct
87 Correct 651 ms 37580 KB Output is correct
88 Correct 815 ms 13232 KB Output is correct
89 Correct 790 ms 7008 KB Output is correct
90 Correct 761 ms 2540 KB Output is correct
91 Correct 603 ms 1144 KB Output is correct
92 Correct 636 ms 1524 KB Output is correct
93 Correct 668 ms 20484 KB Output is correct
94 Correct 604 ms 10356 KB Output is correct
95 Correct 507 ms 15036 KB Output is correct
96 Correct 458 ms 7676 KB Output is correct
97 Correct 636 ms 20088 KB Output is correct
98 Correct 605 ms 10336 KB Output is correct
99 Correct 203 ms 632 KB Output is correct
100 Correct 14 ms 384 KB Output is correct
101 Correct 13 ms 832 KB Output is correct
102 Execution timed out 5078 ms 848284 KB Time limit exceeded
103 Halted 0 ms 0 KB -