oj.uz

Submission #292673

# Submission time Handle Problem Language Result Execution time Memory
292673 2020-09-07T11:37:01 Z 최은수(#5797) Express 20/19 (ROI19_express) C++17
67 / 100
 5000 ms 679584 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 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;)
    {
        vector<ll>curv;
        for(pl&t:adj[i])
            for(ll&t2:vv[t.fi])
                curv.eb(t2+t.se);
        sort(all(curv));
        for(ll&t:curv)
        {
            if((int)vv[i].size()>1&&t*(p-1)<=vv[i][(int)vv[i].size()-2]*p)
                vv[i].pop_back();
            vv[i].eb(t);
        }
    }
    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 0 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 1 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 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 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 8 ms 384 KB Output is correct
13 Correct 9 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 7 ms 384 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 8 ms 384 KB Output is correct
19 Correct 8 ms 384 KB Output is correct
20 Correct 11 ms 384 KB Output is correct
21 Correct 9 ms 384 KB Output is correct
22 Correct 8 ms 384 KB Output is correct
23 Correct 8 ms 384 KB Output is correct
24 Correct 7 ms 384 KB Output is correct
25 Correct 7 ms 384 KB Output is correct
26 Correct 7 ms 384 KB Output is correct
27 Correct 6 ms 396 KB Output is correct
28 Correct 6 ms 392 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 6 ms 384 KB Output is correct

Subtask #2
24.0 / 24.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 1 ms 360 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 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 4 ms 384 KB Output is correct
11 Correct 15 ms 896 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 8 ms 768 KB Output is correct
14 Correct 5 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 5 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 5 ms 744 KB Output is correct
23 Correct 6 ms 760 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 4 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 4 ms 384 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 37 ms 4592 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 438 ms 34552 KB Output is correct
3 Correct 368 ms 7544 KB Output is correct
4 Correct 341 ms 4000 KB Output is correct
5 Correct 294 ms 1180 KB Output is correct
6 Correct 374 ms 11404 KB Output is correct
7 Correct 350 ms 6348 KB Output is correct
8 Correct 376 ms 11872 KB Output is correct
9 Correct 347 ms 6136 KB Output is correct
10 Correct 337 ms 11484 KB Output is correct
11 Correct 318 ms 6024 KB Output is correct
12 Correct 95 ms 512 KB Output is correct
13 Correct 7 ms 384 KB Output is correct
14 Correct 9 ms 360 KB Output is correct
15 Correct 9 ms 384 KB Output is correct
16 Correct 10 ms 384 KB Output is correct
17 Correct 24 ms 384 KB Output is correct
18 Correct 133 ms 1036 KB Output is correct
19 Correct 20 ms 384 KB Output is correct
20 Correct 36 ms 420 KB Output is correct
21 Correct 39 ms 504 KB Output is correct
22 Correct 37 ms 384 KB Output is correct
23 Correct 287 ms 36344 KB Output is correct
24 Correct 834 ms 144196 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 37368 KB Output is correct
2 Correct 734 ms 12944 KB Output is correct
3 Correct 667 ms 6824 KB Output is correct
4 Correct 669 ms 2104 KB Output is correct
5 Correct 527 ms 1000 KB Output is correct
6 Correct 542 ms 1528 KB Output is correct
7 Correct 555 ms 20172 KB Output is correct
8 Correct 476 ms 10232 KB Output is correct
9 Correct 470 ms 16220 KB Output is correct
10 Correct 419 ms 8280 KB Output is correct
11 Correct 538 ms 20172 KB Output is correct
12 Correct 487 ms 10216 KB Output is correct
13 Correct 172 ms 632 KB Output is correct
14 Correct 11 ms 384 KB Output is correct
15 Correct 10 ms 832 KB Output is correct
16 Execution timed out 5141 ms 675904 KB Time limit exceeded
17 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 1 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 4 ms 1408 KB Output is correct
9 Correct 2 ms 384 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 524 KB Output is correct
18 Correct 6 ms 896 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 1152 KB Output is correct
22 Correct 3 ms 768 KB Output is correct
23 Correct 6 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 3 ms 384 KB Output is correct
36 Correct 4 ms 384 KB Output is correct
37 Correct 5 ms 512 KB Output is correct
38 Correct 5 ms 384 KB Output is correct
39 Correct 5 ms 384 KB Output is correct
40 Correct 4 ms 384 KB Output is correct
41 Correct 5 ms 384 KB Output is correct
42 Correct 4 ms 384 KB Output is correct
43 Correct 18 ms 2552 KB Output is correct
44 Correct 17 ms 2432 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 9968 KB Output is correct
2 Correct 1486 ms 41664 KB Output is correct
3 Correct 809 ms 47944 KB Output is correct
4 Correct 562 ms 1432 KB Output is correct
5 Correct 438 ms 1624 KB Output is correct
6 Correct 429 ms 1124 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 31 ms 384 KB Output is correct
10 Correct 13 ms 384 KB Output is correct
11 Correct 331 ms 1288 KB Output is correct
12 Correct 1446 ms 1548 KB Output is correct
13 Correct 644 ms 1204 KB Output is correct
14 Correct 407 ms 1548 KB Output is correct
15 Correct 1347 ms 1416 KB Output is correct
16 Correct 396 ms 2592 KB Output is correct
17 Correct 1214 ms 21736 KB Output is correct
18 Execution timed out 5065 ms 16172 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 9940 KB Output is correct
2 Correct 1491 ms 41704 KB Output is correct
3 Correct 800 ms 47864 KB Output is correct
4 Correct 506 ms 1736 KB Output is correct
5 Correct 455 ms 1016 KB Output is correct
6 Correct 466 ms 1016 KB Output is correct
7 Correct 422 ms 1312 KB Output is correct
8 Correct 376 ms 1004 KB Output is correct
9 Correct 591 ms 11816 KB Output is correct
10 Correct 608 ms 9432 KB Output is correct
11 Correct 588 ms 11820 KB Output is correct
12 Correct 575 ms 8900 KB Output is correct
13 Correct 551 ms 11772 KB Output is correct
14 Correct 548 ms 9708 KB Output is correct
15 Correct 177 ms 632 KB Output is correct
16 Correct 180 ms 632 KB Output is correct
17 Correct 160 ms 504 KB Output is correct
18 Correct 65 ms 512 KB Output is correct
19 Correct 327 ms 888 KB Output is correct
20 Correct 384 ms 888 KB Output is correct
21 Correct 365 ms 956 KB Output is correct
22 Correct 609 ms 156724 KB Output is correct
23 Correct 912 ms 265740 KB Output is correct
24 Correct 659 ms 5520 KB Output is correct
25 Execution timed out 5135 ms 679584 KB Time limit exceeded
26 Halted 0 ms 0 KB -