oj.uz

Submission #851281

# Submission time Handle Problem Language Result Execution time Memory
851281 2023-09-19T10:02:07 Z kderylo Toll (BOI17_toll) C++17
15 / 100
 99 ms 21640 KB 
#include <iostream>
using namespace std;
const int stala=5e4+10;
int tab[stala][6][16];
long long pom[10][16];
void prepare(int ile,int k)
{
    for(int z=1;z<16;z++){
        for(int i=0;i<ile;i++){
            int pocz=i/k;
            int sr=pocz+(1<<(z-1));
            int kon=pocz+(1<<z);
            if(kon*k<=ile){
                int sr_x=min(sr*k,ile-1);
                int sr_y=min((sr+1)*k-1,ile-1);
                int kon_x=min(kon*k,ile-1);
                int kon_y=min((kon+1)*k-1,ile-1);
                for(int x=sr_x;x<=sr_y;x++){
                    for(int y=kon_x;y<=kon_y;y++){
                        tab[i][y%k][z]=min(tab[i][y%k][z],tab[i][x%k][z-1]+tab[x][y%k][z-1]);
                    }
                }
            }
        }
    }
}
int find_path(int x,int y,int k,int ile)
{
    for(int i=0;i<k;i++){
        for(int j=1;j<16;j++){
            pom[i][j]=1e9;
        }
    }
    int group_x=x/k;
    int group_y=y/k;
    if(group_x>=group_y){
        return -1;
    }
    int roznica=group_y-group_x;
    int l=0;
    for(int i=15;i>=0;i--){
        if((roznica&(1<<i))>0){
            l++;
            if(l==1){
                for(int j=0;j<k;j++){
                    pom[j][l]=tab[x][j][i];
                }
                group_x+=(1<<i);
            }
            else{
                int pocz_x=min(group_x*k,ile-1);
                int pocz_y=min((group_x+1)*k-1,ile-1);
                int kon_x=min(group_y*k,ile-1);
                int kon_y=min((group_y+1)*k-1,ile-1);
                for(int x=pocz_x;x<=pocz_y;x++){
                    for(int y=kon_x;y<=kon_y;y++){
                        pom[y%k][l]=min(pom[y%k][l],pom[x%k][l-1]+tab[x][y%k][i]);
                    }
                }
                group_x+=(1<<i);
            }
        }
    }
    if(pom[y%k][l]<1e9){
        return pom[y%k][l];
    }
    else{
        return -1;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k,n,m,o;
    cin>>k>>n>>m>>o;
    for(int i=0;i<=n;i++){
        for(int j=0;j<k;j++){
            for(int z=0;z<16;z++){
                tab[i][j][z]=1e9;
            }
        }
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        tab[a][b%k][0]=c;
    }
    prepare(n,k);
    for(int i=1;i<=o;i++){
        int a,b;
        cin>>a>>b;
        cout<<find_path(a,b,k,n)<<"\n";
    }

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19280 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 35 ms 20060 KB Output is correct
9 Correct 31 ms 20056 KB Output is correct
10 Correct 20 ms 19288 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19228 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 4 ms 2648 KB Output is correct
8 Correct 6 ms 2648 KB Output is correct
9 Correct 36 ms 20048 KB Output is correct
10 Correct 90 ms 21328 KB Output is correct
11 Correct 70 ms 20816 KB Output is correct
12 Correct 79 ms 20512 KB Output is correct
13 Incorrect 92 ms 15220 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2648 KB Output is correct
10 Correct 28 ms 19800 KB Output is correct
11 Correct 79 ms 20756 KB Output is correct
12 Correct 89 ms 21336 KB Output is correct
13 Correct 84 ms 21640 KB Output is correct
14 Correct 89 ms 21072 KB Output is correct
15 Correct 89 ms 14364 KB Output is correct
16 Correct 79 ms 13912 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2648 KB Output is correct
10 Correct 28 ms 19800 KB Output is correct
11 Correct 79 ms 20756 KB Output is correct
12 Correct 89 ms 21336 KB Output is correct
13 Correct 84 ms 21640 KB Output is correct
14 Correct 89 ms 21072 KB Output is correct
15 Correct 89 ms 14364 KB Output is correct
16 Correct 79 ms 13912 KB Output is correct
17 Correct 80 ms 20820 KB Output is correct
18 Correct 1 ms 504 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 2 ms 2808 KB Output is correct
24 Correct 3 ms 2648 KB Output is correct
25 Correct 4 ms 2648 KB Output is correct
26 Correct 4 ms 2652 KB Output is correct
27 Correct 27 ms 20056 KB Output is correct
28 Correct 97 ms 21272 KB Output is correct
29 Incorrect 99 ms 21516 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19280 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 35 ms 20060 KB Output is correct
9 Correct 31 ms 20056 KB Output is correct
10 Correct 20 ms 19288 KB Output is correct
11 Correct 66 ms 19228 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 500 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 4 ms 2648 KB Output is correct
18 Correct 6 ms 2648 KB Output is correct
19 Correct 36 ms 20048 KB Output is correct
20 Correct 90 ms 21328 KB Output is correct
21 Correct 70 ms 20816 KB Output is correct
22 Correct 79 ms 20512 KB Output is correct
23 Incorrect 92 ms 15220 KB Output isn't correct
24 Halted 0 ms 0 KB -