oj.uz

Submission #585158

# Submission time Handle Problem Language Result Execution time Memory
585158 2022-06-28T11:12:40 Z Huy Toll (BOI17_toll) C++17
7 / 100
 150 ms 46540 KB 
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,ll>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e9 + 1;
const int maxN = (int)5e4 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const int infty = 1e15 + 7;
const int base = (int)4e5;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int k,n,m,o;
ll f[maxN][17][5];
ll jump[maxN][5];
int grp;
map<pii,int> edg;

void Read()
{
    cin >> k >> n >> m >> o;
    for(int i = 1;i <= m;i++)
    {
        int a,b,t;
        cin >> a >> b >> t;
        edg[{a,b}] = edg[{b,a}] = t;
    }
}

void Solve()
{
    for(int i = n - 1;i >= 0;i--)
    {
        /// j = 0;
        for(int d = 0;d < k;d++)
        {
            int nxt = (i / k + 1) * k + d;
            if(edg.find(make_pair(i,nxt)) == edg.end()) f[i][0][d] = infty;
            else f[i][0][d] = edg[{i,nxt}];
        }

        for(int j = 1;j <= (int)log2(n);j++)
        {
            for(int d = 0;d < k;d++)
            {
                f[i][j][d] = infty;
                for(int d1 = 0;d1 < k;d1++) /// pre d
                {
                    int nxt = (i / k + (1<<(j-1))) * k + d1;
                    if(nxt <= n) f[i][j][d] = min(f[i][j][d],f[nxt][j-1][d] + f[i][j-1][d1]);
                    else
                    {
                        f[i][j][d] = min(f[i][j][d],f[i][j-1][d1]);
                    }
                }
            }
        }
    }

    while(o--)
    {
        int x,y;
        cin >> x >> y;
        if(x > y) cout << -1 <<'\n';
        else if(x == y) cout << 0 <<'\n';
        else
        {
            int dis = y / k - x / k;
            int pre = x / k;
            for(int i = (int)log2(n);i >= 0;i--)
            {
                if(dis & (1 << i))
                {
                    int nxt = pre + (1 << i);
                    if(pre == x/k)
                    {
                        for(int d = 0;d < k;d++)
                        {
                            jump[nxt][d] = f[x][i][d];
                        }
                    }
                    else
                    {
                        for(int d = 0;d < k;d++)
                        {
                            jump[nxt][d] = infty;
                            for(int d1 = 0;d1 < k;d1++)
                            {
                                jump[nxt][d] = min(jump[nxt][d],jump[pre][d1]+f[pre*k+d1][i][d]);
                            }
                        }
                    }
                    pre = nxt;
                }
            }
            int res = jump[y/k][y%k];
            if(res >= infty) res = -1;
            cout << res <<'\n';
        }
    }

    //cout <<"dcme"<<' '<< f[4][0][2] <<' '<<'\n';
}

void Debug()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message

toll.cpp:19:24: warning: overflow in conversion from 'double' to 'int' changes value from '1.000000000000007e+15' to '2147483647' [-Woverflow]
   19 | const int infty = 1e15 + 7;
      |                   ~~~~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 41932 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 87 ms 42708 KB Output is correct
9 Correct 110 ms 42376 KB Output is correct
10 Correct 42 ms 35640 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 46540 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 41932 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 87 ms 42708 KB Output is correct
9 Correct 110 ms 42376 KB Output is correct
10 Correct 42 ms 35640 KB Output is correct
11 Correct 150 ms 46540 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -