oj.uz

Submission #783738

# Submission time Handle Problem Language Result Execution time Memory
783738 2023-07-15T09:26:46 Z 1075508020060209tc Toll (BOI17_toll) C++14
7 / 100
 132 ms 190796 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int K;int n;int m;int O;
vector<pair<int,int>>e[500005];
int jmp[18][100005][5][5];
int nwgr[10][10];
int tmpgr[10][10];
int agr[10][10];
int bgr[10][10];
void mrg(int pl){
for(int i=0;i<=K-1;i++){
    for(int j=0;j<=K-1;j++){
        tmpgr[i][j]=1e18;
    }
}
for(int a=0;a<=K-1;a++){
    for(int aa=0;aa<=K-1;aa++){
        int apl=aa+K*(pl);
        for(int i=0;i<e[apl].size();i++){
            int v=e[apl][i].first;
            v%=K;
            int w=e[apl][i].second;
            for(int b=0;b<=K-1;b++){
                tmpgr[a][b]=min(tmpgr[a][b],agr[a][aa]+w+bgr[v][b]);
            }
        }
    }
}
}


signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>K>>n>>m>>O;

for(int i=1;i<=m;i++){
    int a;int b;int t;
    cin>>a>>b>>t;
    e[a].push_back({b,t});
}
for(int lg=0;lg<=17;lg++){
    for(int a=0;a<=K-1;a++){
        for(int b=0;b<=K-1;b++){
            for(int i=0;i<=n+1;i++){
                if(a==b&&lg==0){continue;}
                jmp[lg][i][a][b]=1e18;
            }
        }
    }
}
for(int lg=1;lg<=17;lg++){
    for(int i=0;i+(1<<lg)-1<=n/K+1;i++){
        for(int a=0;a<=K-1;a++){
            for(int aa=0;aa<=K-1;aa++){
                int apl=K*(i+(1<<(lg-1))-1)+aa;
                for(int j=0;j<e[apl].size();j++){
                    int v=e[apl][j].first;
                    v%=K;
                    int w=e[apl][j].second;
                    for(int b=0;b<=K-1;b++){
                        jmp[lg][i][a][b]=min(jmp[lg][i][a][b],jmp[lg-1][i][a][aa]+w+jmp[lg-1][i+(1<<(lg-1))][v][b]);
                    }
                }

            }
        }
    }
}


while(O--){
    int a;int b;
    cin>>a>>b;
    if( (a/K)>=(b/K)){
        cout<<-1<<endl;
    }
    for(int i=0;i<=K-1;i++){
        for(int j=0;j<=K-1;j++){
            if(i==j&&((a%K)==i)){
                nwgr[i][j]=0;
                continue;
            }
            nwgr[i][j]=1e18;
        }
    }
    int nwpl=a/K;
    for(int lg=17;lg>=0;lg--){
        if(nwpl+(1<<lg)<=(b/K)){
        //    cout<<lg<<endl;
            for(int i=0;i<=K-1;i++){
                for(int j=0;j<=K-1;j++){
                    agr[i][j]=nwgr[i][j];
                }
            }
            for(int i=0;i<=K-1;i++){
                for(int j=0;j<=K-1;j++){
                    bgr[i][j]=jmp[lg][nwpl+1][i][j];
                }
            }
            mrg(nwpl);
            nwpl+=(1<<lg);
            for(int i=0;i<=K-1;i++){
                for(int j=0;j<=K-1;j++){
                    nwgr[i][j]=tmpgr[i][j];
                }
            }
        }
    }
    int ans=nwgr[a%K][b%K];
    if(ans>=1e18){
        ans=-1;
    }
    cout<<ans<<endl;

}
return 0;
int lg;int i;int a;int b;
while(cin>>lg>>i>>a>>b){
    cout<<jmp[lg][i][a][b]<<endl;
}




}

Compilation message

toll.cpp: In function 'void mrg(long long int)':
toll.cpp:22:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i=0;i<e[apl].size();i++){
      |                     ~^~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:60:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 for(int j=0;j<e[apl].size();j++){
      |                             ~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 180152 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Correct 6 ms 12244 KB Output is correct
4 Correct 6 ms 12212 KB Output is correct
5 Correct 9 ms 15572 KB Output is correct
6 Correct 10 ms 15544 KB Output is correct
7 Correct 10 ms 15572 KB Output is correct
8 Correct 105 ms 180044 KB Output is correct
9 Correct 108 ms 180016 KB Output is correct
10 Correct 79 ms 178504 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 190796 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Incorrect 6 ms 12244 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 180152 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Correct 6 ms 12244 KB Output is correct
4 Correct 6 ms 12212 KB Output is correct
5 Correct 9 ms 15572 KB Output is correct
6 Correct 10 ms 15544 KB Output is correct
7 Correct 10 ms 15572 KB Output is correct
8 Correct 105 ms 180044 KB Output is correct
9 Correct 108 ms 180016 KB Output is correct
10 Correct 79 ms 178504 KB Output is correct
11 Correct 132 ms 190796 KB Output is correct
12 Correct 6 ms 12244 KB Output is correct
13 Incorrect 6 ms 12244 KB Output isn't correct
14 Halted 0 ms 0 KB -