oj.uz

Submission #472553

# Submission time Handle Problem Language Result Execution time Memory
472553 2021-09-13T17:52:40 Z Blobo2_Blobo2 Toll (BOI17_toll) C++14
18 / 100
 3000 ms 6080 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() <= 10)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 3097 ms 5964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5196 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 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 8 ms 1800 KB Output is correct
8 Correct 10 ms 1848 KB Output is correct
9 Correct 39 ms 5272 KB Output is correct
10 Correct 72 ms 6080 KB Output is correct
11 Correct 59 ms 5280 KB Output is correct
12 Correct 42 ms 5152 KB Output is correct
13 Correct 89 ms 5184 KB Output is correct
14 Correct 43 ms 4176 KB Output is correct
15 Correct 35 ms 3844 KB Output is correct
16 Correct 36 ms 3812 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 1356 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1484 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 1484 KB Output is correct
8 Correct 8 ms 1484 KB Output is correct
9 Correct 6 ms 1484 KB Output is correct
10 Correct 35 ms 4548 KB Output is correct
11 Correct 170 ms 4620 KB Output is correct
12 Correct 227 ms 5484 KB Output is correct
13 Correct 281 ms 5776 KB Output is correct
14 Correct 231 ms 5112 KB Output is correct
15 Correct 149 ms 3672 KB Output is correct
16 Correct 135 ms 3736 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 1356 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1484 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 1484 KB Output is correct
8 Correct 8 ms 1484 KB Output is correct
9 Correct 6 ms 1484 KB Output is correct
10 Correct 35 ms 4548 KB Output is correct
11 Correct 170 ms 4620 KB Output is correct
12 Correct 227 ms 5484 KB Output is correct
13 Correct 281 ms 5776 KB Output is correct
14 Correct 231 ms 5112 KB Output is correct
15 Correct 149 ms 3672 KB Output is correct
16 Correct 135 ms 3736 KB Output is correct
17 Execution timed out 3067 ms 5040 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 3097 ms 5964 KB Time limit exceeded
2 Halted 0 ms 0 KB -