| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097157 |
2024-10-06T10:16:25 Z |
vjudge1 |
Toll (BOI17_toll) |
C++17 |
|
259 ms |
71248 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
template<class T,class U,class trtr,class lztr,class lzlz> struct segtree{
vector<T> seg;
vector<U> d;
trtr TT;
lztr UT;
lzlz UU;
T Tid;
U Uid;
int n;
int lg;
segtree(T Tid,U Uid,trtr TT,lztr UT,lzlz UU): Tid(Tid),Uid(Uid),TT(TT),UT(UT),UU(UU){};
void refresh(int v){
seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
}
void build(vector<T> &a){
int siz=a.size();
n=1;
while(n<siz){
n<<=1;
}
lg=__lg(n);
seg.assign(n<<1,Tid);
d.assign(n,Uid);
copy(a.begin(),a.end(),seg.begin()+n);
for(int i=n-1;i>1;i--){
refresh(i);
}
}
void apply(int v,U f){
seg[v]=UT(f,seg[v]);
if(v<n){
d[v]=UU(f,d[v]);
}
}
void push(int v){
apply(v<<1,d[v]);
apply((v<<1)|1,d[v]);
d[v]=Uid;
}
void update(int l,int r,U f){
if(l==r){
return;
}
l+=n,r+=n;
int l0=l,r0=r;
for(int i=lg;i>=1;i--){
if((l>>i<<i)!=l){
push(l>>i);
}
if((r>>i<<i)!=r){
push(r>>i);
}
}
for(;l<r;l>>=1,r>>=1){
if(l&1){
apply(l,f);
l++;
}
if(r&1){
r--;
apply(r,f);
}
}
l=l0,r=r0;
for(int i=1;i<=lg;i++){
if((l>>i<<i)!=l){
refresh(l>>i);
}
if((r>>i<<i)!=r){
refresh(r>>i);
}
}
}
T query(int l,int r){
if(l==r){
return Tid;
}
l+=n,r+=n;
for(int i=lg;i>=1;i--){
if((l>>i<<i)!=l){
push(l>>i);
}
if((r>>i<<i)!=r){
push(r>>i);
}
}
T trl=Tid,trr=Tid;
for(;l<r;l>>=1,r>>=1){
if(l&1){
trl=TT(trl,seg[l]);
l++;
}
if(r&1){
r--;
trr=TT(seg[r],trr);
}
}
return TT(trl,trr);
}
};
class T{
public:
vector<vector<int>> mat;
T(): mat(5,vector<int>(5,1e18)){};
};
class U{
public:
int temp;
U(): temp(-1){};
};
vector<vector<int>> multiply(vector<vector<int>> &a,vector<vector<int>> &b){
vector<vector<int>> curr(a.size(),vector<int>(5,1e18));
for(int i=0;i<a.size();i++){
for(int k=0;k<5;k++){
for(int j=0;j<5;j++){
curr[i][j]=min(curr[i][j],a[i][k]+b[k][j]);
}
}
}
return curr;
}
class trtr{
public:
T operator()(T &trl,T &trr){
T pa;
pa.mat=multiply(trl.mat,trr.mat);
return pa;
}
};
class lztr{
public:
T operator()(U &app,T &tr){
return tr;
}
};
class lzlz{
public:
U operator()(U &app,U &lz){
return lz;
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
trtr TT;
lztr UT;
lzlz UU;
T Tid;
U Uid;
segtree<T,U,trtr,lztr,lzlz> seg(Tid,Uid,TT,UT,UU);
int k,n,m,o;
cin >> k >> n >> m >> o;
vector<T> a(n/k+1);
for(int i=0;i<m;i++){
int u,v,t;
cin >> u >> v >> t;
a[u/k].mat[u%k][v%k]=t;
}
seg.build(a);
while(o--){
int u,v;
cin >> u >> v;
if(u/k==v/k){
cout << -1 << endl;
continue;
}
vector<vector<int>> base(1,vector<int>(5,1e18));
base[0][u%k]=0;
T trans=seg.query(u/k,v/k);
base=multiply(base,trans.mat);
if(base[0][v%k]==1e18){
base[0][v%k]=-1;
}
cout << base[0][v%k] << endl;
}
}
Compilation message
toll.cpp: In function 'std::vector<std::vector<long long int> > multiply(std::vector<std::vector<long long int> >&, std::vector<std::vector<long long int> >&)':
toll.cpp:117:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
toll.cpp: In instantiation of 'segtree<T, U, trtr, lztr, lzlz>::segtree(T, U, trtr, lztr, lzlz) [with T = T; U = U; trtr = trtr; lztr = lztr; lzlz = lzlz]':
toll.cpp:154:53: required from here
toll.cpp:12:7: warning: 'segtree<T, U, trtr, lztr, lzlz>::Uid' will be initialized after [-Wreorder]
12 | U Uid;
| ^~~
toll.cpp:8:10: warning: 'trtr segtree<T, U, trtr, lztr, lzlz>::TT' [-Wreorder]
8 | trtr TT;
| ^~
toll.cpp:15:5: warning: when initialized here [-Wreorder]
15 | segtree(T Tid,U Uid,trtr TT,lztr UT,lzlz UU): Tid(Tid),Uid(Uid),TT(TT),UT(UT),UU(UU){};
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
259 ms |
71248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
36948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
259 ms |
71248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
