oj.uz

Submission #1109632

# Submission time Handle Problem Language Result Execution time Memory
1109632 2024-11-07T08:01:03 Z theSkeleton Toll (BOI17_toll) C++17
8 / 100
 3000 ms 94280 KB 
//!!in the name of god!!
#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e9
#define F first
#define S second
#define PB push_back
#define PF push_front
#define pll pair<ll,ll>
#define pii pair<int,int>
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define MT(a,b,c) make_tuple(a,b,c)
#define has(a,b) (a.find(b)!=a.end())
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const int mx = 5e4+5;
const int lg = 32;
map<int,ll> adj[mx][lg];
int glg(int v){
    if(v<2)return 0;
    return glg(v/2)+1;
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int k,n,m,o;
    cin>>k>>n>>m>>o;
    for(int u,v,t;m--;)
        cin>>u>>v>>t,
        adj[u][0][v]=t;
    for(int t=0;t<n;t++)
    for(int p=1;p<lg;p++){
        for(auto e:adj[t][p-1])
        for(auto d:adj[e.F][p-1])
        if(has(adj[t][p],d.F))
            adj[t][p][d.F]=min(adj[t][p][d.F],e.S+d.S);
        else
            adj[t][p][d.F]=e.S+d.S;
    }
    for(int a,b;o--;){
        cin>>a>>b;
        int c=a/k,t=b/k;
        map<int,ll> cn,te;
        cn[a]=0;
        while(c<t){
            te.clear();
            int ne=glg(c-t);
            for(auto e:cn)
                for(auto d:adj[e.F][ne])
                    if(has(te,d.F))
                        te[d.F]=min(te[d.F],e.S+d.S);
                    else te[d.F]=e.S+d.S;
            cn=te;
            c+=1<<ne;
        }
        if(has(cn,b)) cout<<cn[b]<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 81896 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 3052 ms 87624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 75600 KB Output is correct
2 Correct 14 ms 75376 KB Output is correct
3 Correct 14 ms 75612 KB Output is correct
4 Correct 13 ms 75600 KB Output is correct
5 Correct 13 ms 75600 KB Output is correct
6 Correct 13 ms 75600 KB Output is correct
7 Correct 17 ms 75856 KB Output is correct
8 Correct 18 ms 76112 KB Output is correct
9 Correct 17 ms 75856 KB Output is correct
10 Correct 61 ms 82516 KB Output is correct
11 Correct 189 ms 87636 KB Output is correct
12 Correct 231 ms 93372 KB Output is correct
13 Correct 265 ms 94280 KB Output is correct
14 Correct 228 ms 91244 KB Output is correct
15 Correct 170 ms 87368 KB Output is correct
16 Correct 153 ms 87368 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 75600 KB Output is correct
2 Correct 14 ms 75376 KB Output is correct
3 Correct 14 ms 75612 KB Output is correct
4 Correct 13 ms 75600 KB Output is correct
5 Correct 13 ms 75600 KB Output is correct
6 Correct 13 ms 75600 KB Output is correct
7 Correct 17 ms 75856 KB Output is correct
8 Correct 18 ms 76112 KB Output is correct
9 Correct 17 ms 75856 KB Output is correct
10 Correct 61 ms 82516 KB Output is correct
11 Correct 189 ms 87636 KB Output is correct
12 Correct 231 ms 93372 KB Output is correct
13 Correct 265 ms 94280 KB Output is correct
14 Correct 228 ms 91244 KB Output is correct
15 Correct 170 ms 87368 KB Output is correct
16 Correct 153 ms 87368 KB Output is correct
17 Execution timed out 3076 ms 87776 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 3061 ms 81896 KB Time limit exceeded
2 Halted 0 ms 0 KB -