oj.uz

Submission #472551

# Submission time Handle Problem Language Result Execution time Memory
472551 2021-09-13T17:51:04 Z Blobo2_Blobo2 Toll (BOI17_toll) C++14
8 / 100
 3000 ms 6036 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<long long> & d) {
    d.assign(n, INF);
    d[s] = 0;
    using pii = pair<long long, 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 long long dijkstra2(int s,int to) {
    vector<long long>d;
    d.assign(n, INF);
    d[s] = 0;
    using pii = pair<long long, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        long long 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()*n <= n*n)continue;
        vector<long long>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 3079 ms 6036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

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 1380 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1540 KB Output is correct
7 Correct 4 ms 1612 KB Output is correct
8 Correct 8 ms 1612 KB Output is correct
9 Correct 6 ms 1484 KB Output is correct
10 Correct 28 ms 4644 KB Output is correct
11 Correct 200 ms 4592 KB Output is correct
12 Correct 236 ms 5464 KB Output is correct
13 Correct 325 ms 5808 KB Output is correct
14 Correct 218 ms 5064 KB Output is correct
15 Correct 157 ms 3708 KB Output is correct
16 Correct 138 ms 3724 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 1380 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1540 KB Output is correct
7 Correct 4 ms 1612 KB Output is correct
8 Correct 8 ms 1612 KB Output is correct
9 Correct 6 ms 1484 KB Output is correct
10 Correct 28 ms 4644 KB Output is correct
11 Correct 200 ms 4592 KB Output is correct
12 Correct 236 ms 5464 KB Output is correct
13 Correct 325 ms 5808 KB Output is correct
14 Correct 218 ms 5064 KB Output is correct
15 Correct 157 ms 3708 KB Output is correct
16 Correct 138 ms 3724 KB Output is correct
17 Execution timed out 3026 ms 5124 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 3079 ms 6036 KB Time limit exceeded
2 Halted 0 ms 0 KB -