oj.uz

Submission #631019

# Submission time Handle Problem Language Result Execution time Memory
631019 2022-08-17T13:57:05 Z Tuanlinh123 Toll (BOI17_toll) C++17
7 / 100
 95 ms 40976 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/freopen/"

vector <pll> A[500005];

struct Sparse
{
    ll n, k, num;
    vector <ll> lg;
    vector <vector <vector <vector <ll>>>> sp;

    Sparse(ll n, ll k): n(n), k(k)
    {
        num=n/k+1;
        lg.resize(n+6);
        for (ll i=2; i<=n+5; i++)
            lg[i]=lg[i/2]+1;
        sp.resize(k+1);
        for (ll i=0; i<k; i++)
        {
            sp[i].resize(num+5);
            for (ll j=0; j<=num; j++)
            {
                sp[i][j].resize(k+5);
                for (ll z=0; z<k; z++)
                    sp[i][j][z].assign(lg[num]+5, 1000000000000);
            }
        }
        for (ll i=0; i<k; i++)
        {
            for (ll j=0; j<num; j++)
            {
                ll u=j*k+i;
                for (ll z=0; z<A[u].size(); z++)
                {
                    ll v=A[u][z].fi, dis=A[u][z].se;
                    if (v/k != u/k+1)
                        continue;
                    sp[i][j][v%k][0]=min(sp[i][j][v%k][0], dis);
                    // cout << i << " " << j << " " << v%k << " " << sp[i][j][v%k][0] << " " << u << " " << v << "\n";
                }
            }
        }
        // for (ll i=0; i<k; i++)
        //     for (ll j=0; j<num; j++)
        //         for (ll z=0; z<k; z++)
        //             for (ll k1=0; k1<=lg[num]; k1++)
        //                 cout << i << " " << j << " " << z << " " << k1 << " " << sp[i][j][z][k1] << " debug\n";
        for (ll l=1; l<=lg[num]; l++)
        {
            for (ll j=0; j+(1<<l)<num; j++)
            {
                for (ll i=0; i<k; i++)
                {
                    for (ll k1=0; k1<k; k1++)
                    {
                        for (ll z=0; z<k; z++)
                        {
                            sp[i][j][k1][l]=min(sp[i][j][k1][l], sp[i][j][z][l-1]+sp[z][j+(1<<(l-1))][k1][l-1]);
                            // cout << i << " " << j << " " << z << " " << sp[i][j][z][l-1] << "\n";
                            // cout << z << " " << j+(1<<(l-1)) << " " << k1 << " " << sp[z][j+(1<<(l-1))][k1][l-1] << "\n";
                        }
                        // cout << i << " " << j << " " << k1 << " " << l << " " << sp[i][j][k1][l] << "\n";
                    }
                }
            }
        }
    }

    ll query(ll a, ll b)
    {
        ll i1=a%k, j1=a/k, i2=b%k, j2=b/k;
        ll dif=j2-j1; ll Min[k], nMin[k];
        for (ll i=0; i<k; i++)
            Min[i]=100000000000;
        Min[i1]=0;
        ll step=0, crr=j1;
        while (dif>0)
        {
            // cout << "bruh" << flush;
            if (dif&1)
            {
                // cout << crr << " " << step << "\n";
                for (ll i=0; i<k; i++)
                {
                    // cout << Min[i] << " ";
                    nMin[i]=Min[i], Min[i]=1000000000000;
                }
                // cout << "\n";
                for (ll i=0; i<k; i++)
                {
                    for (ll ii=0; ii<k; ii++)
                    {
                        Min[i]=min(Min[i], nMin[ii]+sp[ii][crr][i][step]);
                    }
                }
                // for (ll i=0; i<k; i++)
                //     cout << Min[i] << " ";
                // cout << "\n";
                crr+=(1<<step);
            }
            step++;
            dif>>=1;
        }
        // cout << crr << " " << step << "\n";
        // for (ll i=0; i<k; i++)
        //     cout << Min[i] << " ";
        // cout << "\n";
        // cout << a << " " << b << " " << Min[i2] << "\n";
        return Min[i2];
    }
};

int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);    
    ll k, n, m, o; cin >> k >> n >> m >> o;
    for (ll i=1; i<=m; i++)
    {
        ll x, y, z; cin >> x >> y >> z;
        if (x>y) swap(x, y);
        A[x].pb({y, z});
    }
    Sparse B(n, k);
    // cout << "bruh " << flush;
    for (ll i=0; i<o; i++)
    {
        ll x, y; cin >> x >> y;
        ll ans=B.query(x, y);
        if (ans==1000000000000)
            cout << -1 << "\n";
        else cout << ans << "\n";
    }
}

Compilation message

toll.cpp: In constructor 'Sparse::Sparse(long long int, long long int)':
toll.cpp:44:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                 for (ll z=0; z<A[u].size(); z++)
      |                              ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 31996 KB Output is correct
2 Correct 8 ms 11948 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 7 ms 12372 KB Output is correct
6 Correct 7 ms 12396 KB Output is correct
7 Correct 7 ms 12372 KB Output is correct
8 Correct 60 ms 32028 KB Output is correct
9 Correct 56 ms 31856 KB Output is correct
10 Correct 40 ms 30112 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 40976 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Incorrect 6 ms 11988 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Incorrect 6 ms 12068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Incorrect 6 ms 12068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 31996 KB Output is correct
2 Correct 8 ms 11948 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 7 ms 12372 KB Output is correct
6 Correct 7 ms 12396 KB Output is correct
7 Correct 7 ms 12372 KB Output is correct
8 Correct 60 ms 32028 KB Output is correct
9 Correct 56 ms 31856 KB Output is correct
10 Correct 40 ms 30112 KB Output is correct
11 Correct 95 ms 40976 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Incorrect 6 ms 11988 KB Output isn't correct
14 Halted 0 ms 0 KB -