oj.uz

Submission #472564

# Submission time Handle Problem Language Result Execution time Memory
472564 2021-09-13T18:05:59 Z Blobo2_Blobo2 Toll (BOI17_toll) C++14
18 / 100
 3000 ms 5584 KB 
/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);
#define EPS 0.00000001

const int mo=1e9+7,INF=1e9;
int nxt(){int x;cin>>x;return x;}
vector<pair<int,int> >adj[50001];
int n;
inline void dijkstra(int s, vector<int> & d) {
    d.assign(n, INF);
    d[s] = 0;
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;

        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                q.push({d[to], to});
            }
        }
    }
}
inline int dijkstra2(int s,int to) {
    vector<int>d;
    d.assign(n, INF);
    d[s] = 0;
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;
        if(v == to)
            return d_v;
        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                q.push({d[to], to});
            }
        }
    }
    return INF;
}
signed main(){
    Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
    //freopen("in.txt","r",stdin);
    int k=nxt();
    n=nxt();
    int m=nxt(),qu=nxt();
    for(int i=0;i<m;i++){
        int x = nxt(),y=nxt(),c= nxt();
        adj[x].push_back({y,c});
    }
    unordered_set<int>from;
    int finalAns[qu];
    vector<pair<int,int> >v;
    vector<pair<int,int>>ans[n];
    for(int i=0;i<qu;i++){
        v.push_back({nxt(),nxt()});
        finalAns[i] = -2;
        if(v.back().first == v.back().second)
            finalAns[i] = 0;
        else if(v.back().first/k >= v.back().second/k)
            finalAns[i] = -1;
        else
            ans[v.back().first].push_back({v.back().second,i});
        from.insert(v.back().first);
    }
    for(auto x:from){
        if(ans[x].size() <= 100)continue;
        vector<int>d;
        dijkstra(x,d);
        for(auto y:ans[x])
            finalAns[y.second] = (d[y.first] == INF?-1:d[y.first]);
    }
    for(int i=0;i<qu;i++){
        if(finalAns[i] == -2){
            int zh2t = dijkstra2(v[i].first,v[i].second);
            cout<<(zh2t == INF?-1:zh2t)<<endl;
        }
        else cout<<finalAns[i]<<endl;
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 5300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4872 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 2 ms 1356 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 4 ms 1868 KB Output is correct
8 Correct 5 ms 1868 KB Output is correct
9 Correct 24 ms 4700 KB Output is correct
10 Correct 68 ms 5532 KB Output is correct
11 Correct 50 ms 4756 KB Output is correct
12 Correct 41 ms 4624 KB Output is correct
13 Correct 66 ms 5060 KB Output is correct
14 Correct 41 ms 4044 KB Output is correct
15 Correct 34 ms 3700 KB Output is correct
16 Correct 34 ms 3652 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 4 ms 1484 KB Output is correct
8 Correct 8 ms 1484 KB Output is correct
9 Correct 7 ms 1484 KB Output is correct
10 Correct 32 ms 4404 KB Output is correct
11 Correct 157 ms 4452 KB Output is correct
12 Correct 228 ms 5316 KB Output is correct
13 Correct 268 ms 5584 KB Output is correct
14 Correct 209 ms 4896 KB Output is correct
15 Correct 147 ms 3512 KB Output is correct
16 Correct 125 ms 3648 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 4 ms 1484 KB Output is correct
8 Correct 8 ms 1484 KB Output is correct
9 Correct 7 ms 1484 KB Output is correct
10 Correct 32 ms 4404 KB Output is correct
11 Correct 157 ms 4452 KB Output is correct
12 Correct 228 ms 5316 KB Output is correct
13 Correct 268 ms 5584 KB Output is correct
14 Correct 209 ms 4896 KB Output is correct
15 Correct 147 ms 3512 KB Output is correct
16 Correct 125 ms 3648 KB Output is correct
17 Execution timed out 3071 ms 4792 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 5300 KB Time limit exceeded
2 Halted 0 ms 0 KB -