oj.uz

Submission #648759

# Submission time Handle Problem Language Result Execution time Memory
648759 2022-10-08T03:46:32 Z PoonYaPat Toll (BOI17_toll) C++14
0 / 100
 96 ms 85036 KB 
#include <bits/stdc++.h>
using namespace std;

const int sq=2;
int k,n,m,q;
int dis[50001][17][5][5]; //(a,b,x,y) : from ak+x to (a+(1<<b))k+y

void merge(int ans[5][5], int a[5][5], int b[5][5]) {
    for (int i=0; i<k; ++i) {
        for (int j=0; j<k; ++j) {
            //find ans[i][j]
            for (int z=0; z<k; ++z) {
                ans[i][j]=min(ans[i][j],a[i][z]+b[z][j]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>k>>n>>m>>q;
    memset(dis,0x3f,sizeof(dis));

    for (int i=0; i<m; ++i) {
        int a,b,w;
        cin>>a>>b>>w;
        dis[a/k][0][a%k][b%k]=w;
    }

    for (int i=1; i<17; ++i) {
        for (int j=0; j+(1<<i)<=n/k; ++j) {
            merge(dis[j][i],dis[j][i-1],dis[j+(1<<(i-1))][i-1]);
        }
    }

    while (q--) {
        int x,y; cin>>x>>y;
        int group=x/k;
        //from x/k to y/k

        int ans[5][5],temp[5][5];
        memset(ans,0x3f,sizeof(ans));
        for (int i=0; i<k; ++i) ans[i][i]=0;

        for (int i=16; i>=0; --i) {
            if (group+(1<<i)<=y/k) {
                memset(temp,0x3f,sizeof(temp));
                merge(temp,ans,dis[x/k][i]);
                swap(temp,ans);
                group+=(1<<i);
            }
        }
        if (ans[x%k][y%k]==0x3f3f3f3f) cout<<-1<<"\n";
        else cout<<ans[x%k][y%k]<<"\n";
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 84428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 85036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 84428 KB Output isn't correct
2 Halted 0 ms 0 KB -