oj.uz

Submission #1101884

# Submission time Handle Problem Language Result Execution time Memory
1101884 2024-10-17T06:29:29 Z simona1230 Toll (BOI17_toll) C++17
0 / 100
 674 ms 524288 KB 
// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;

int k,n,m,o;
vector<pair<int,int> > v[50001];
long long d[50001][16][8][8];

void read()
{
    cin>>k>>n>>m>>o;
    
    for(int b=0;b<=(n-1)/k;b++)
        for(int i1=0;i1<k;i1++)
            for(int i2=0;i2<k;i2++)
                d[b][0][i1][i2]=1e9;
                
    for(int i=1;i<=m;i++)
    {
        int a,b;
        long long t;
        cin>>a>>b>>t;
        v[a].push_back({b,t});
        int b1=a/k;
        int i1=a%k;
        int i2=b%k;
        d[b1][0][i1][i2]=min(d[b1][0][i1][i2],t);
    }
}

void prec()
{
    for(int lg=1;lg<16;lg++)
        for(int i1=0;i1<k;i1++)
            for(int i2=0;i2<k;i2++)
                for(int b=0;b<=(n-1)/k;b++)
                    {
                        d[b][lg][i1][i2]=1e9;
                        for(int i3=0;i3<k;i3++)
                             d[b][lg][i1][i2]=min(d[b][lg-1][i1][i3]
                                +d[b+(1<<(lg-1))][lg-1][i3][i2],
                                    d[b][lg][i1][i2]);
                    }
}


long long ans[8],ans2[8];
void compute(int a,int b)
{
    for(int i=0;i<k;i++)
        ans[i]=1e9;
    ans[a%k]=0;
    
    int jump=b/k-a/k;
    int block=a/k;
    for(int lg=0;lg<16;lg++)
    {
        if((1<<lg)&jump)
        {
            for(int i=0;i<k;i++)
                ans2[i]=ans[i];
            for(int i2=0;i2<k;i2++)
            {
                ans[i2]=1e9;
                for(int i1=0;i1<k;i1++)
                    ans[i2]=min(ans[i2],ans2[i1]+d[block][lg][i1][i2]);
            }
            block+=(1<<lg);
        }
    }
    
    int i=b%k;
    if(ans[i]>=1e9)cout<<-1<<endl;
    else cout<<ans[i]<<endl;
}

void solve()
{
    for(int i=1;i<=o;i++)
    {
        int a,b;
        cin>>a>>b;
        compute(a,b);
    }
}

int main() {
    read();
    prec();
    solve();
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 629 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 204668 KB Output is correct
2 Correct 2 ms 1616 KB Output is correct
3 Correct 1 ms 1616 KB Output is correct
4 Correct 1 ms 1616 KB Output is correct
5 Correct 2 ms 1616 KB Output is correct
6 Correct 2 ms 1616 KB Output is correct
7 Correct 27 ms 10064 KB Output is correct
8 Correct 21 ms 6192 KB Output is correct
9 Runtime error 622 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1616 KB Output is correct
2 Correct 2 ms 1616 KB Output is correct
3 Correct 2 ms 1616 KB Output is correct
4 Correct 1 ms 1616 KB Output is correct
5 Correct 1 ms 1616 KB Output is correct
6 Correct 3 ms 10064 KB Output is correct
7 Correct 3 ms 5968 KB Output is correct
8 Correct 6 ms 4088 KB Output is correct
9 Correct 5 ms 3920 KB Output is correct
10 Runtime error 674 ms 524288 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1616 KB Output is correct
2 Correct 2 ms 1616 KB Output is correct
3 Correct 2 ms 1616 KB Output is correct
4 Correct 1 ms 1616 KB Output is correct
5 Correct 1 ms 1616 KB Output is correct
6 Correct 3 ms 10064 KB Output is correct
7 Correct 3 ms 5968 KB Output is correct
8 Correct 6 ms 4088 KB Output is correct
9 Correct 5 ms 3920 KB Output is correct
10 Runtime error 674 ms 524288 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 629 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -