Submission #878334

#	Time	Username	Problem	Language	Result	Execution time	Memory
878334		Danet	Toll (BOI17_toll)	C++14	0 / 100	151 ms	180720 KiB

toll

/****************************D A N E T****************************
***  ██████╗     █████╗    ███╗   ██╗   ███████╗   ████████╗   ***
***	 ██╔══██╗   ██╔══██╗   ████╗  ██║   ██╔════╝   ╚══██╔══╝   ***
***	 ██║  ██║   ███████║   ██╔██╗ ██║   █████╗        ██║      ***
***	 ██║  ██║   ██╔══██║   ██║╚██╗██║   ██╔══╝        ██║      ***
***	 ██████╔╝   ██║  ██║   ██║ ╚████║   ███████╗      ██║      ***
***	 ╚═════╝    ╚═╝  ╚═╝   ╚═╝  ╚═══╝   ╚══════╝               ***                              
****************************D A N E T****************************/
#include <bits/stdc++.h>
using namespace std;
/**************************P R A G M As**************************/
#pragma GCC optimize("O3")
/**************************D E F I N Es**************************/
#define Tof_Io  		ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
//#define int  			long long int
#define double  		long double
#define pb				push_back
#define endl 			'\n'
#define cond(x)	   		x = x/ l;
/*****************D E F I N Es-F U N C T I O Nes*****************/
#define debug(x)    	cerr << #x << ": " << x << endl
#define kill(x)     	cout << x << endl, exit(0)
#define all(x) 			x.begin(),x.end()
/***************************C O N S Ty***************************/
const double 			PI = 3.141592653589793;
const int 				mod = 1e9+7;//1e9+7 998244353
const int 				inf = 1e9+9;
const int 				N = 1e5+3;
const int 				logt = 18;
/***************************B U I L Dy***************************/
int fac[N];
int inv[N];
vector<int> adj[N];
int dp[N][5][5][logt];
int mt[2][5][5];
int n;
int l;
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
/****************************N O T Ey****************************/
/*

*/
/***********************F U N C T I O N es***********************/
int  dnt_pow	(int a, int b, int md = mod){int ans = 1; while(b){if(b&1){ans = (a*ans)%md;}a = (a*a)%md;b >>= 1;}return ans ;}
void dnt_bld	(){fac[0] = 1; inv[0] = dnt_pow(fac[0],mod-2) ;for(int i = 1 ; i < N ; i++) {fac[i] = (fac[i-1] * i) % mod;inv[i] = dnt_pow( fac[i] , mod-2);}}
int  dnt_lis	(vector<int> v){if (v.size() == 0) {return 0;} vector<int> vc(v.size(), 0); int len = 1; vc[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = vc.begin(), e = vc.begin() + len; auto it = lower_bound(b, e, v[i]); if (it == vc.begin() + len){vc[len++] = v[i];}else{*it = v[i];}} return len;}
int  dnt_ncr	(int n,int r){return fac[n] * inv[r] % mod * inv[n-r] % mod;}
void dnt_clen	(){for (int i = 0; i < 5; i++) mt[0][i][i] = 0;}
/********************************************************************************************************************************/ 
void slv(int absa)
{
	for (int i = 0; i + (1 << absa) - 1 <= n / l + 1; i++) 
	{
		for (int i1 = 0; i1 < l; i1++)
			for (int i2 = 0; i2 < l; i2++) 
			{
				for (int i3 = 0; i3 < l; i3++) 
				{
					int cnt = dp[i][i1][i3][absa - 1] + dp[i + (1 << absa - 1)][i3][i2][absa - 1];
					dp[i][i1][i2][absa] = min(dp[i][i1][i2][absa], cnt);
				}
			}
	}
}
void solve()
{
    int a, b;
    cin >> a >> b;
    int i1 = a % l;
    int i2 = b % l;
	cond(a);
	cond(b);
    memset(mt, 60, sizeof(mt));
	dnt_clen();
    for (int i = 0; i < 5; i++) mt[0][i][i] = 0;
    int cr = 0;
    for (int i = logt; i >= 0; i--) 
    {
        if (a + (1 << i) <= b) 
        {
            for (int i1 = 0; i1 < 5; i1++)
                for (int i2 = 0; i2 < 5; i2++)
                    for (int i3 = 0; i3 < 5; i3++)
                        {
                            int cnt = mt[cr][i1][i3] + dp[a][i3][i2][i];
                            if(cnt < mt[cr ^1][i1][i2])
                            {
                                mt[cr^1][i1][i2] = cnt;
                            }
                        }    
            memset(mt[cr], 60, sizeof(mt[cr]));
            a += (1 << i);
            cr = cr ^ 1;
        }
    }
    if (mt[cr][i1][i2] > inf)
    {
        cout << -1;
        return;
    }
    cout << mt[cr][i1][i2];
}
int32_t main()
{
    cin >> l;
    int n , m;
    cin >> n >> m;  
    int q;
    cin >> q;
    memset(dp, 60, sizeof(dp));
    for(int i = 0; i < m ; i++)
    {
        int u, v;
        cin >> u >> v;
        int w;
        cin >> w;
        dp[u/l][u%l][v%l][0] = min(dp[u/l][u%l][v%l][0], w);
    }
    for (int i = 1; (1 << i) <= n / l + 1; i++) 
    {
		slv(i);
    }
    while (q--) 
    {
        solve();
        cout << endl;
    }
}



	

Compilation message (stderr)

toll.cpp: In function 'int dnt_lis(std::vector<int>)':
toll.cpp:46:135: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 | int  dnt_lis (vector<int> v){if (v.size() == 0) {return 0;} vector<int> vc(v.size(), 0); int len = 1; vc[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = vc.begin(), e = vc.begin() + len; auto it = lower_bound(b, e, v[i]); if (it == vc.begin() + len){vc[len++] = v[i];}else{*it = v[i];}} return len;}
      |                                                                                                                                     ~~^~~~~~~~~~
toll.cpp: In function 'void slv(int)':
toll.cpp:59:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   59 |      int cnt = dp[i][i1][i3][absa - 1] + dp[i + (1 << absa - 1)][i3][i2][absa - 1];
      |                                                       ~~~~~^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44