oj.uz

Submission #472555

# Submission time Handle Problem Language Result Execution time Memory
472555 2021-09-13T17:53:48 Z Blobo2_Blobo2 Toll (BOI17_toll) C++14
18 / 100
 3000 ms 6392 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;
    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;
        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;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:79:9: warning: unused variable 'k' [-Wunused-variable]
   79 |     int k=nxt();
      |         ^

Subtask #1
0 / 7.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5524 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 1480 KB Output is correct
7 Correct 8 ms 1868 KB Output is correct
8 Correct 8 ms 1884 KB Output is correct
9 Correct 32 ms 5620 KB Output is correct
10 Correct 74 ms 6392 KB Output is correct
11 Correct 55 ms 5528 KB Output is correct
12 Correct 41 ms 5412 KB Output is correct
13 Correct 96 ms 5560 KB Output is correct
14 Correct 43 ms 4644 KB Output is correct
15 Correct 37 ms 4300 KB Output is correct
16 Correct 37 ms 4316 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 2 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 3 ms 1484 KB Output is correct
7 Correct 4 ms 1484 KB Output is correct
8 Correct 8 ms 1628 KB Output is correct
9 Correct 6 ms 1628 KB Output is correct
10 Correct 29 ms 4892 KB Output is correct
11 Correct 164 ms 4932 KB Output is correct
12 Correct 220 ms 5828 KB Output is correct
13 Correct 254 ms 6100 KB Output is correct
14 Correct 209 ms 5432 KB Output is correct
15 Correct 153 ms 4168 KB Output is correct
16 Correct 118 ms 4048 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 2 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 3 ms 1484 KB Output is correct
7 Correct 4 ms 1484 KB Output is correct
8 Correct 8 ms 1628 KB Output is correct
9 Correct 6 ms 1628 KB Output is correct
10 Correct 29 ms 4892 KB Output is correct
11 Correct 164 ms 4932 KB Output is correct
12 Correct 220 ms 5828 KB Output is correct
13 Correct 254 ms 6100 KB Output is correct
14 Correct 209 ms 5432 KB Output is correct
15 Correct 153 ms 4168 KB Output is correct
16 Correct 118 ms 4048 KB Output is correct
17 Execution timed out 3076 ms 5360 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 3084 ms 6308 KB Time limit exceeded
2 Halted 0 ms 0 KB -