oj.uz

Submission #472557

# Submission time Handle Problem Language Result Execution time Memory
472557 2021-09-13T17:58:43 Z Blobo2_Blobo2 Toll (BOI17_toll) C++14
18 / 100
 3000 ms 6896 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
    //reopen("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;
    map<pair<int,int>,int>finalAns;
    vector<pair<int,int> >v;
    vector<int>ans[n];
    while(qu--){
        v.push_back({nxt(),nxt()});
        finalAns[v.back()] = -2;
        if(v.back().first == v.back().second)finalAns[v.back()] = 0;
        else if(v.back().first/k >= v.back().second/k) finalAns[v.back()] = -1;
        else ans[v.back().first].push_back(v.back().second);
        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[{x,y}] = (d[y] == INF?-1:d[y]);
    }
    for(auto x:v){
        if(finalAns[x] == -2){
            int zh2t = dijkstra2(x.first,x.second);
            cout<<(zh2t == INF?-1:zh2t)<<endl;
        }
        else cout<<finalAns[x]<<endl;
    }
    return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6212 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 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 8 ms 1996 KB Output is correct
8 Correct 8 ms 1916 KB Output is correct
9 Correct 31 ms 5872 KB Output is correct
10 Correct 72 ms 6896 KB Output is correct
11 Correct 55 ms 6008 KB Output is correct
12 Correct 43 ms 5992 KB Output is correct
13 Correct 74 ms 6120 KB Output is correct
14 Correct 45 ms 5080 KB Output is correct
15 Correct 37 ms 4740 KB Output is correct
16 Correct 36 ms 4832 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 1488 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1488 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 4 ms 1496 KB Output is correct
8 Correct 8 ms 1672 KB Output is correct
9 Correct 6 ms 1628 KB Output is correct
10 Correct 27 ms 5244 KB Output is correct
11 Correct 156 ms 5480 KB Output is correct
12 Correct 221 ms 6448 KB Output is correct
13 Correct 265 ms 6604 KB Output is correct
14 Correct 215 ms 5948 KB Output is correct
15 Correct 143 ms 4616 KB Output is correct
16 Correct 122 ms 4616 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 1488 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1488 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 4 ms 1496 KB Output is correct
8 Correct 8 ms 1672 KB Output is correct
9 Correct 6 ms 1628 KB Output is correct
10 Correct 27 ms 5244 KB Output is correct
11 Correct 156 ms 5480 KB Output is correct
12 Correct 221 ms 6448 KB Output is correct
13 Correct 265 ms 6604 KB Output is correct
14 Correct 215 ms 5948 KB Output is correct
15 Correct 143 ms 4616 KB Output is correct
16 Correct 122 ms 4616 KB Output is correct
17 Execution timed out 3056 ms 5880 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 3034 ms 6712 KB Time limit exceeded
2 Halted 0 ms 0 KB -