oj.uz

Submission #1109633

# Submission time Handle Problem Language Result Execution time Memory
1109633 2024-11-07T08:03:36 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;
    }
    map<int,ll> cn,te;
    for(int a,b;o--;){
        cin>>a>>b;
        int c=a/k,t=b/k;
        cn.clear();
        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 3051 ms 81876 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 3038 ms 87880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 75616 KB Output is correct
2 Correct 13 ms 75600 KB Output is correct
3 Correct 13 ms 75600 KB Output is correct
4 Correct 14 ms 75600 KB Output is correct
5 Correct 13 ms 75600 KB Output is correct
6 Correct 15 ms 75600 KB Output is correct
7 Correct 17 ms 75856 KB Output is correct
8 Correct 19 ms 76112 KB Output is correct
9 Correct 20 ms 75856 KB Output is correct
10 Correct 56 ms 81632 KB Output is correct
11 Correct 190 ms 87732 KB Output is correct
12 Correct 238 ms 93172 KB Output is correct
13 Correct 269 ms 94280 KB Output is correct
14 Correct 220 ms 91208 KB Output is correct
15 Correct 172 ms 87368 KB Output is correct
16 Correct 143 ms 87236 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 75616 KB Output is correct
2 Correct 13 ms 75600 KB Output is correct
3 Correct 13 ms 75600 KB Output is correct
4 Correct 14 ms 75600 KB Output is correct
5 Correct 13 ms 75600 KB Output is correct
6 Correct 15 ms 75600 KB Output is correct
7 Correct 17 ms 75856 KB Output is correct
8 Correct 19 ms 76112 KB Output is correct
9 Correct 20 ms 75856 KB Output is correct
10 Correct 56 ms 81632 KB Output is correct
11 Correct 190 ms 87732 KB Output is correct
12 Correct 238 ms 93172 KB Output is correct
13 Correct 269 ms 94280 KB Output is correct
14 Correct 220 ms 91208 KB Output is correct
15 Correct 172 ms 87368 KB Output is correct
16 Correct 143 ms 87236 KB Output is correct
17 Execution timed out 3042 ms 87772 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 3051 ms 81876 KB Time limit exceeded
2 Halted 0 ms 0 KB -