oj.uz

Submission #843052

# Submission time Handle Problem Language Result Execution time Memory
843052 2023-09-03T15:29:21 Z ASN49K Toll (BOI17_toll) C++14
7 / 100
 141 ms 73624 KB 
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <set>
#include <functional>
#include <bitset>
#include <map>
#include <unordered_map>
#include <queue>
#include <array>
#include <numeric>
#include <complex>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream& os, vector<A>& a) { for(auto &c:a)os<<c<<' '; return os;}
template<typename A> istream& operator>>(istream& os, vector<A>& a) { for(auto &c:a)os>>c; return os;}
template<typename A,size_t N> istream& operator>>(istream &os, array<A,N>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,typename B> istream& operator>>(istream& os, pair<A,B>&a) { os>>a.first>>a.second; return os;}
template<typename A> istream& operator >>(istream& os,complex<A>& a){pair<A,A>aux;os>>aux;a=complex<A>(aux.first,aux.second);return os;}
#define bug(a) cerr << "(" << #a << ": " << a << ")\n";
#define all(x) x.begin(),x.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define PQ priority_queue
#define x real
#define y imag
using pii= pair<int,int>;
using VI= vector<int>;
using v64= vector<int64_t>;
using point=complex<double>;
using i64= int64_t;
using i16= int16_t;
using u64= uint64_t;
using u32= uint32_t;
using i32= int32_t;
using u16= uint16_t;
const i32 inf=1e9;
const i64 INF=1e18;
const int mod=1e9+7;
const int sigma=26;
///sparse table dp[(int)log2(saritura)][poz/k][x][y]
#define vvii vector<vector<int>>
void solve()
{
    int k,n,m,q;
    cin>>k>>n>>m>>q;
    int mx_jump=(n-1)/k;
    //position of last element
    vector<vector<vector<vector<int>>>>dp((int)log2(mx_jump)+1,vector<vector<vector<int>>>(mx_jump+1,vector<vector<int>>(k,vector<int>(k,inf))));
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        dp[0][x/k][x%k][y%k]=z;
    }
    auto combine=[&](const vvii& x,const vvii& y)
    {
        vvii sol(k,vector<int>(k,inf));
        for(int i=0;i<k;i++)
        {
            for(int j=0;j<k;j++)
            {
                for(int m=0;m<k;m++)
                {
                    sol[i][j]=min(sol[i][j],x[i][m]+y[m][j]);
                }
            }
        }
        return sol;

    };
    for(int i=1;(1<<i)-1<=mx_jump;i++)
    {
        for(int j=0;j+(1<<i)-1<=mx_jump;j++)
        {
            dp[i][j]=combine(dp[i-1][j],dp[i-1][j+(1<<(i-1))]);
        }
    }
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        vector<int> sol(5,inf);
        sol[x%k]=0;
        int caut=y%k;
        x/=k;
        y/=k;
        if(x!=y)
        {
            for(int i=(int)log2(y-x);i>=0;i--)
            {
                if(x+(1<<i)<=y)
                {
                    auto old=sol;
                    fill(all(sol),inf);
                    for(int a=0;a<k;a++)
                    {
                        for(int b=0;b<k;b++)
                        {
                            sol[b]=min(sol[b],old[a]+dp[i][x][a][b]);
                        }
                    }
                    x+=(1<<i);
                }
            }
        }
        if(sol[caut]==inf)
            sol[caut]=-1;
        cout<<sol[caut]<<'\n';

    }
}
main()
{
    i32 tt=1;
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cin>>tt;
    while(tt--)
    {
        solve();
    }
}

Compilation message

toll.cpp:118:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  118 | main()
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 73624 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 1420 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 2 ms 1372 KB Output is correct
8 Correct 138 ms 73420 KB Output is correct
9 Correct 132 ms 73556 KB Output is correct
10 Correct 120 ms 73460 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 61056 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 1 ms 456 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 73624 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 1420 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 2 ms 1372 KB Output is correct
8 Correct 138 ms 73420 KB Output is correct
9 Correct 132 ms 73556 KB Output is correct
10 Correct 120 ms 73460 KB Output is correct
11 Correct 109 ms 61056 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -