oj.uz

Submission #292678

# Submission time Handle Problem Language Result Execution time Memory
292678 2020-09-07T11:42:12 Z 최은수(#5797) Express 20/19 (ROI19_express) C++17
28 / 100
 3767 ms 1027804 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;
        int i1=adj[i][0].fi,i2=adj[i][1].fi;
        ll w1=adj[i][0].se,w2=adj[i][1].se;
        int j=0,k=0;
        while(j<(int)vv[i1].size()&&k<(int)vv[i2].size())
        {
            if(vv[i1][j]+w1<vv[i2][k]+w2)
                curv.eb(vv[i1][j]+w1),j++;
            else
                curv.eb(vv[i2][k]+w2),k++;
        }
        while(j<(int)vv[i1].size()||k<(int)vv[i2].size())
        {
            if(j<(int)vv[i1].size())
                curv.eb(vv[i1][j]+w1),j++;
            else
                curv.eb(vv[i2][k]+w2),k++;
        }
        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
0 / 15.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 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 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 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 Runtime error 6 ms 512 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 380 KB Output is correct
10 Runtime error 3 ms 640 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 469 ms 34576 KB Output is correct
3 Correct 365 ms 7628 KB Output is correct
4 Correct 344 ms 4004 KB Output is correct
5 Correct 306 ms 1100 KB Output is correct
6 Correct 368 ms 11384 KB Output is correct
7 Correct 378 ms 6304 KB Output is correct
8 Correct 380 ms 11876 KB Output is correct
9 Correct 385 ms 6136 KB Output is correct
10 Correct 352 ms 11484 KB Output is correct
11 Correct 295 ms 6024 KB Output is correct
12 Correct 101 ms 512 KB Output is correct
13 Correct 8 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 10 ms 384 KB Output is correct
16 Correct 14 ms 432 KB Output is correct
17 Correct 24 ms 384 KB Output is correct
18 Correct 148 ms 1080 KB Output is correct
19 Correct 19 ms 384 KB Output is correct
20 Correct 39 ms 384 KB Output is correct
21 Correct 54 ms 504 KB Output is correct
22 Correct 41 ms 384 KB Output is correct
23 Correct 249 ms 36472 KB Output is correct
24 Correct 743 ms 144208 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 37316 KB Output is correct
2 Correct 739 ms 12972 KB Output is correct
3 Correct 706 ms 6936 KB Output is correct
4 Correct 645 ms 2112 KB Output is correct
5 Correct 580 ms 908 KB Output is correct
6 Correct 598 ms 1488 KB Output is correct
7 Correct 592 ms 20244 KB Output is correct
8 Correct 568 ms 10360 KB Output is correct
9 Correct 550 ms 16196 KB Output is correct
10 Correct 411 ms 8200 KB Output is correct
11 Correct 529 ms 20096 KB Output is correct
12 Correct 505 ms 10240 KB Output is correct
13 Correct 160 ms 640 KB Output is correct
14 Correct 12 ms 384 KB Output is correct
15 Correct 10 ms 832 KB Output is correct
16 Correct 3767 ms 1027216 KB Output is correct
17 Correct 3647 ms 1027804 KB Output is correct

Subtask #5
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 Runtime error 1 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 165 ms 11444 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 11328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -