oj.uz

Submission #56833

# Submission time Handle Problem Language Result Execution time Memory
56833 2018-07-12T19:09:33 Z Hoppa 버스 (JOI14_bus) C++14
100 / 100
 935 ms 257820 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int n,m,q,val;
vector<ii> g[100005];
struct data
{
    int u,v,ti,to;
} a[300005];
int cmp(data x,data y)
{
    return x.to<y.to;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
        cin>>a[i].u>>a[i].v>>a[i].ti>>a[i].to;
    sort(a+1,a+1+m,cmp);
    for(int i=1; i<=m; i++)
    {
        if(a[i].u==1)
        {
            ii tmp=ii(a[i].to,a[i].ti);
            if(g[a[i].v].size()>0)
                tmp.second=max(tmp.second,g[a[i].v].back().second);
            g[a[i].v].push_back(tmp);
        }
        else
        {
            int rs=-1,l=0,r=g[a[i].u].size()-1;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(g[a[i].u][mid].first<=a[i].ti)
                {
                    rs=g[a[i].u][mid].second;
                    l=mid+1;
                }
                else r=mid-1;
            }
            if(rs!=-1)
            {
                ii tmp=ii(a[i].to,rs);
                if(g[a[i].v].size()>0)
                    tmp.second=max(tmp.second,g[a[i].v].back().second);
                g[a[i].v].push_back(tmp);
            }
        }
    }
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>val;
       int ans=-1,l=0,r=g[n].size()-1;
       while(l<=r)
       {
           int mid=(l+r)/2;
           if(g[n][mid].first<=val)
           {
               ans=g[n][mid].second;
               l=mid+1;
           }
           else r=mid-1;
       }
       cout<<ans<<"\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 5 ms 2948 KB Output is correct
3 Correct 7 ms 3096 KB Output is correct
4 Correct 5 ms 3096 KB Output is correct
5 Correct 5 ms 3120 KB Output is correct
6 Correct 6 ms 3172 KB Output is correct
7 Correct 5 ms 3372 KB Output is correct
8 Correct 5 ms 3372 KB Output is correct
9 Correct 7 ms 3448 KB Output is correct
10 Correct 4 ms 3448 KB Output is correct
11 Correct 11 ms 3480 KB Output is correct
12 Correct 10 ms 3524 KB Output is correct
13 Correct 8 ms 3584 KB Output is correct
14 Correct 12 ms 3616 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3668 KB Output is correct
2 Correct 285 ms 5412 KB Output is correct
3 Correct 251 ms 6228 KB Output is correct
4 Correct 25 ms 6228 KB Output is correct
5 Correct 27 ms 6228 KB Output is correct
6 Correct 22 ms 6228 KB Output is correct
7 Correct 185 ms 6276 KB Output is correct
8 Correct 5 ms 6276 KB Output is correct
9 Correct 193 ms 6644 KB Output is correct
10 Correct 235 ms 8116 KB Output is correct
11 Correct 213 ms 8132 KB Output is correct
12 Correct 252 ms 9636 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 22128 KB Output is correct
2 Correct 605 ms 30872 KB Output is correct
3 Correct 669 ms 39504 KB Output is correct
4 Correct 594 ms 48208 KB Output is correct
5 Correct 760 ms 56872 KB Output is correct
6 Correct 543 ms 65548 KB Output is correct
7 Correct 582 ms 74468 KB Output is correct
8 Correct 646 ms 83320 KB Output is correct
9 Correct 676 ms 91184 KB Output is correct
10 Correct 585 ms 100364 KB Output is correct
11 Correct 527 ms 108024 KB Output is correct
12 Correct 521 ms 115296 KB Output is correct
13 Correct 543 ms 122648 KB Output is correct
14 Correct 496 ms 130188 KB Output is correct
15 Correct 498 ms 137704 KB Output is correct
16 Correct 199 ms 137880 KB Output is correct
17 Correct 234 ms 139968 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 148628 KB Output is correct
2 Correct 777 ms 157536 KB Output is correct
3 Correct 838 ms 166864 KB Output is correct
4 Correct 870 ms 175104 KB Output is correct
5 Correct 739 ms 182488 KB Output is correct
6 Correct 812 ms 191376 KB Output is correct
7 Correct 914 ms 200076 KB Output is correct
8 Correct 842 ms 207404 KB Output is correct
9 Correct 805 ms 215292 KB Output is correct
10 Correct 817 ms 224172 KB Output is correct
11 Correct 795 ms 230840 KB Output is correct
12 Correct 858 ms 237740 KB Output is correct
13 Correct 935 ms 244580 KB Output is correct
14 Correct 790 ms 251352 KB Output is correct
15 Correct 738 ms 257820 KB Output is correct
16 Correct 394 ms 257820 KB Output is correct