oj.uz

Submission #766133

# Submission time Handle Problem Language Result Execution time Memory
766133 2023-06-25T10:33:02 Z bachhoangxuan 버스 (JOI14_bus) C++17
100 / 100
 175 ms 27060 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define pii pair<int,int>
struct ed{
    int u,t,id,a;
    bool operator<(ed o){
        if(t!=o.t) return t<o.t;
        else return a<o.a;
    }
};
int n,m,d[3*maxn],Max[maxn];
vector<pii> dist[maxn];
vector<ed> e;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v,s,t;cin >> u >> v >> s >> t;
        e.push_back({u,s,i,1});
        e.push_back({v,t,i,0});
    }
    for(int i=1;i<=n;i++) Max[i]=-1;
    sort(e.begin(),e.end());
    for(ed x:e){
        if(x.a==1){
            if(x.u==1) d[x.id]=x.t;
            else d[x.id]=Max[x.u];
        }
        else{
            if(d[x.id]!=-1){
                dist[x.u].push_back({x.t,d[x.id]});
                Max[x.u]=max(Max[x.u],d[x.id]);
            }
        }
    }
    for(int i=1;i<(int)dist[n].size();i++) dist[n][i].second=max(dist[n][i].second,dist[n][i-1].second);
    int q;cin >> q;
    while(q--){
        int x;cin >> x;
        int p=upper_bound(dist[n].begin(),dist[n].end(),make_pair(x,INT_MAX))-dist[n].begin();
        if(p==0) cout << -1 << '\n';
        else cout << dist[n][p-1].second << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2772 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 18 ms 4276 KB Output is correct
3 Correct 18 ms 4300 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 3 ms 2824 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 14 ms 3284 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 13 ms 3328 KB Output is correct
10 Correct 18 ms 4436 KB Output is correct
11 Correct 15 ms 3540 KB Output is correct
12 Correct 21 ms 4528 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 26924 KB Output is correct
2 Correct 135 ms 27024 KB Output is correct
3 Correct 135 ms 26968 KB Output is correct
4 Correct 133 ms 26960 KB Output is correct
5 Correct 134 ms 26924 KB Output is correct
6 Correct 136 ms 27020 KB Output is correct
7 Correct 134 ms 26432 KB Output is correct
8 Correct 139 ms 26896 KB Output is correct
9 Correct 134 ms 26992 KB Output is correct
10 Correct 131 ms 25760 KB Output is correct
11 Correct 132 ms 25840 KB Output is correct
12 Correct 131 ms 25840 KB Output is correct
13 Correct 132 ms 25772 KB Output is correct
14 Correct 131 ms 25868 KB Output is correct
15 Correct 136 ms 25796 KB Output is correct
16 Correct 47 ms 12120 KB Output is correct
17 Correct 47 ms 12020 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 26924 KB Output is correct
2 Correct 148 ms 26956 KB Output is correct
3 Correct 153 ms 26968 KB Output is correct
4 Correct 149 ms 27004 KB Output is correct
5 Correct 161 ms 26964 KB Output is correct
6 Correct 151 ms 27060 KB Output is correct
7 Correct 156 ms 26452 KB Output is correct
8 Correct 153 ms 26940 KB Output is correct
9 Correct 156 ms 27012 KB Output is correct
10 Correct 151 ms 25820 KB Output is correct
11 Correct 157 ms 25772 KB Output is correct
12 Correct 155 ms 25828 KB Output is correct
13 Correct 159 ms 25772 KB Output is correct
14 Correct 153 ms 25816 KB Output is correct
15 Correct 162 ms 25904 KB Output is correct
16 Correct 67 ms 13152 KB Output is correct