Submission #979336

#TimeUsernameProblemLanguageResultExecution timeMemory
979336lftroqToll (BOI17_toll)C++14
0 / 100
54 ms83680 KiB
/* :-=- :%@@@@@@@@@= .#@@@@@%@%@@@@@@= -@@@@@@@@@@@@@@@@@# .+@@@@@@@@@@@@@@@@@@@@. #@@@@@@@@@@@@@@@@@@@@@% .*@@@@@@@@@@@@@@@@@@@@@@@= / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄\ .@@@@@@@@@@@@@@@@@@@@@@@@# | lftroq ♥ | +@@@@@@@@@@@%%@@@@@@@@@@@@- \_________/ .%@@@@@@@@@@%##%@@@@@@@@@@@# // -@@@@@@@@%%%%%%%%%@@@@@@@@@@: -+- =@@@@@%##%#%##**+#@@@@@@@@@@- .+++.%@@@%##%%%%%%%#**+##%%@@@@@@+ +=*%@@@#*###%%#=--+=+*##%@@@@@@%. :*+%@@*+**##*=======+***#@@@@@@@: =+++**%@###*=++=-==++**#@@@@@@@: .**===*%@@@##+=**#*==***@@@@@@@@@: :+++=+*+%%@@%#==+*%#*+=++@@@@@@@@% .**#*+*+**+%#+=---=***+==*@@@@@@@: :**#*+=+**@%##*%#++++--=++#@@@@@@@+-::. =%**###**#@@%*=*%%%%%*==++++%@@@@@@#=-----. .%@@%***###@@@%*++%%%#*===+=++++%@@@@%*=-----=. =**##+=+##@@@@=+%+=***#%@#+**++++%@@%+=-------=: .++===++====@@@@+--==-=#%%%%+++*++++#%+=------==+=. -++--=++-:::::=#@#----+--*%%*+**+++++++==-----===--+= :*+=--++-::::::--=-----==-=%==+%%***++=---=---===-=++: :*+--+=-::::::::---:----+=-=++##***===-::::-+----=*+: .=--:::.:::-=-::---::--------++--=====-::::--:-==++ :=::::::--::::::--=+-:--++++==++--==:::-:::----==+= *-:::::::.....:-++++++++++++++=+=---::::===-:------ :+:--:......:-+++++++++++++++++====---:--=-=----:-:=. :==--:::.:=+++++++++++++++++++++-::===-:-===-----=--: .+=--:::-:=+++++==++++++++++++++=--:.:-===+-------+=-. .+==-----::-+++-:+++=====+++++++=--=======--:----==+=. :+===-----------:-++====+++++++++=--==--+-:------==-:: +=====-::----+-::-+====+++++++++++=---==:-===:-==-==. :+===========+-::::-----+++++++++++*=--======-=+=-=. .=========++=-::::::----:::-++++++*+=+======+++==. .=========-::::::-----:::=+++++**+=+**====-:. . *======-::::::::-:-----++++++++==++++++- #======-:::::::::-------++++++++====+++= =======-:::::::::----:::=+++++++=====+++ =====---:::::::::::------=++++++===+==++= :===-:--:::::::::::-------+++++++===++=++ .===-:--:::::::::::::-----=+++++====++===. .+=-::--::::::::::::-:-----++++++====++=+: .=-:::--::::::::::::-------=+++++===-----+= .=-:::--:::::::::::---------=++++==-----==+=. .=-:::---:::::::::::---------+++===-----===++. .=::::---:::::::-:-----------=++==-:-----===+- .--:::---:::::::--------------=+=----==--===+- .=::::---::::::::::-------===--==-------=--==: .=--::--::::----:---:::::-:----:::-----======- .=---:--:::---::::::--------------------==++++ */ #include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MOD 1000000007ll #define MOD2 998244353ll #define endl '\n' #define PI acos(-1) #define INFINITE 1000000000 #define INFINITE2 1000000000000000000ll #define llll pair<ll,ll> #define ldld pair<ld,ld> #define fi first #define se second #define sqrt sqrtl typedef long long ll; typedef unsigned long long ull; typedef long double ld; using namespace std; int k,n,m,q; int dp[17][50005][5][5],ans[5][5],temp[5][5]; void solve() { cin >> k >> n >> m >> q; for(int i=0;i<17;i++) for(int j=0;j<=(n+k-1)/k;j++) for(int h=0;h<k;h++) for(int l=0;l<k;l++) dp[i][j][h][l]=INFINITE; while(m--) { int u,v,w; cin >> u >> v >> w; dp[0][u/k][u%k][v%k]=w; } for(int i=1;i<17;i++) { for(int j=0;j+(1<<i)+1<=(n+k-1)/k;j++) { for(int u=0;u<k;u++) { for(int v=0;v<k;v++) { for(int t=0;t<k;t++) dp[i][j][u][v]=min(dp[i][j][u][v],dp[i-1][j][u][t]+dp[i-1][j+(1<<i)-1][t][v]); } } } } while(q--) { int a,b; cin >> a >> b; for(int i=0;i<k;i++) { for(int j=0;j<k;j++) ans[i][j]=INFINITE; ans[i][i]=0; } int x=a/k,y=b/k; for(int i=16;i>=0;i--) { if(x+(1<<i)<=y) { for(int u=0;u<k;u++) for(int v=0;v<k;v++) temp[u][v]=INFINITE; for(int u=0;u<k;u++) for(int v=0;v<k;v++) for(int t=0;t<k;t++) temp[u][v]=min(temp[u][v],ans[u][t]+dp[i][x][t][v]); for(int u=0;u<k;u++) for(int v=0;v<k;v++) ans[u][v]=temp[u][v]; x+=(1<<i); } } if(ans[a%k][b%k]==INFINITE) cout << -1 << endl; else cout << ans[a%k][b%k] << endl; } } int main() { fastIO //freopen("hanhhhh.inp","r",stdin); //freopen("hanhhhh.out","w",stdout); int t=1; //cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...