제출 #1171730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171730		paulxaxa	Toll (BOI17_toll)	C++20	100 / 100	137 ms	21960 KiB

toll

#include <bits/stdc++.h>

#define NMAX 50000
#define LOG 17

#define ll long long int
#define BASE 1024

#define MOD 1000000009


using namespace std;

ifstream fin("cod.in");
ofstream fout("cod.out");

/// dp[i][p][j] = i ->  [i/k] + (1<<p) + j

int dp[NMAX+1][LOG+1][5];

vector<pair<int,int>> adj[NMAX+1];
int k,n,m,q;
int main()
{
    cin >> k >> n >> m >> q;
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
    }
    for(int i=0;i<n;i++)
    {
        for(int p=0;p<=LOG;p++)
        {
            for(int j=0;j<k;j++)
            {
                dp[i][p][j] = 1e9;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(auto [y,c] : adj[i])
        {
            dp[i][0][y-(y/k)*k] = c;
        }
    }
    for(int b=1;b<=LOG;b++)
    {
        for(int i=0;i<n && (i/k) + (1<<b) <= n/k;i++)
        {
            for(int j=0;j<k && ((i/k) + (1<<b))*k + j < n;j++)
            {
                for(int j1=0;j1<k;j1++)
                {
                    dp[i][b][j] = min(dp[i][b][j], dp[i][b-1][j1] + dp[((i/k) + (1<<(b-1)))*k + j1][b-1][j]);
                }
            }
        }
    }
    while(q--)
    {
        int x,y;
        cin >> x >> y;
        if(x/k == y/k)
        {
            cout << -1 << '\n';
        }
        else
        {
            vector<int> dist(k,1e9);
            vector<int> pos(k,0);
            pos[0] = x;
            dist[0] = 0;
            for(int b=LOG;b>=0;b--)
            {
                int curr = pos[0]/k;
                if(curr + (1<<b) <= y/k)
                {
                    vector<int> dist1(k,1e9);
                    vector<int> pos1(k,0);

                    for(int i=0;i<k;i++)
                    {
                        if((curr + (1<<b)) * k + i < n)
                        {
                            pos1[i] = (curr + (1<<b)) * k + i;
                        }
                        for(int j=0;j<k && (curr + (1<<b)) * k + j < n;j++)
                        {
                            dist1[j] = min(dist1[j],dist[i] + dp[pos[i]][b][j]);
                        }
                    }
                    dist = dist1;
                    pos = pos1;
                }
            }
            if(dist[y-(y/k)*k] == 1e9)
            {
                cout << -1 << '\n';
            }
            else
            {
                cout << dist[y-(y/k)*k] << '\n';
            }
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44