fork download
copy 
  1. //ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
  2. //Author: Sazid Hasan
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long              ll;
  7. typedef double                 dl;
  8. typedef vector<int>            vi;
  9. typedef vector<vector<int>>    vii;
  10. typedef vector<ll>             vl;
  11. typedef vector<bool>           vb;
  12. typedef pair<int,int>         pii;
  13. typedef pair<ll, ll>          pll;
  14.  
  15. #define ff                first
  16. #define ss                second
  17. #define all(a)            a.begin(),a.end()
  18. #define gcd(a,b)          __gcd(a,b)
  19. #define lcm(a,b)          (a*(b/gcd(a,b)))
  20. #define file();           freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
  21. #define spc               " "
  22.  
  23. #ifdef ONLINE_JUDGE
  24.     #define debarr(array)
  25.     #define deb(x)
  26.     #define del
  27.     #define debug(...)
  28. #else
  29.     #define debarr(array)  for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
  30.     #define deb(x)         cerr << #x << " = " << x << endl;
  31.     #define del cerr << '\n';
  32.     #define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__);
  33.  
  34.     template <class X, class Y>
  35.     ostream& operator<<(ostream& os, const pair<X, Y>& p) {
  36.         return os << "(" << p.first << ", " << p.second << ")";
  37.     }
  38.  
  39.     template <class Ch, class Tr, class Container>
  40.     basic_ostream<Ch, Tr>& operator<<(basic_ostream<Ch, Tr>& os, const Container& x) {
  41.         int i = 0, n = distance
  42.         (x.begin(), x.end());
  43.         os << "{ ";
  44.         for (const auto& y : x)
  45.             os << y << (++i < n ? ", " : "");
  46.         return os << " }";
  47.     }
  48.  
  49.     template <typename... Args>
  50.     void _debug(const char* names, Args&&... args) {
  51.         string_view s(names);
  52.         cerr << "{ ";
  53.         size_t i = 0, cnt = 0, n = sizeof...(args);
  54.  
  55.         auto next = [&]() {
  56.             while (i < s.size() && (s[i] == ' ' || s[i] == ',')) ++i;
  57.             size_t st = i;
  58.             while (i < s.size() && s[i] != ',') ++i;
  59.             return s.substr(st, i - st);
  60.         };
  61.  
  62.         ((cerr << next() << ": " << args << (++cnt < n ? ", " : "")), ...);
  63.         cerr << " }" << '\n';
  64.     }
  65. #endif
  66.  
  67.  
  68. const double PI =         acos(-1);
  69. const int MOD =           1000000007;
  70. const int inf =           (2147483647);
  71. const ll uinf =           (1LL<<61);
  72. const double EPS =        1e-6;
  73. const int MAXN =          1e5+10;
  74.  
  75. const int adjust = 4005;
  76. const int sz = adjust*2+2;
  77.  
  78.  
  79. class CHT{
  80.     public:
  81.     struct line{
  82.         ll slope, C;
  83.         line(ll slope, ll C): slope(slope), C(C) {}
  84.         ll val(ll x){
  85.             return slope*x + C;
  86.         }
  87.         ll intersect(line & other){
  88.             return (other.C-C + (slope-other.slope-1)) / (slope-other.slope);
  89.         }
  90.     };
  91.     deque<pair<ll, line>> hull;
  92.     void init(vector<ll> & cons, vector<pll> &queries, vl & ans, int going = -1){
  93.         hull.clear();
  94.         sort(all(queries));
  95.         for(int i = sz-1; i >= 0; i--){
  96.             if(cons[i]==uinf) continue;
  97.             line newLine(i-adjust, cons[i]);
  98.             while(hull.size()>0 && hull.back().ff >= hull.back().ss.intersect(newLine)) hull.pop_back();
  99.             if(hull.empty()) hull.push_back({0, newLine});
  100.             else hull.push_back({hull.back().ss.intersect(newLine), newLine});
  101.         }
  102.         for(auto &x: queries){
  103.             ans[x.ss] = min(ans[x.ss], query(x.ff));
  104.         }
  105.     }
  106.     ll query(ll x){
  107.         if(hull.empty()) return uinf;
  108.         while(hull.size()>1 && hull[1].ff <= x) hull.pop_front();
  109.         return hull.front().ss.val(x);
  110.     }
  111. };
  112.  
  113. struct edge{
  114.     int v, cost, r;
  115.     edge(){
  116.         cin >> v >> cost >> r;
  117.     }
  118. };
  119.  
  120. bool solve(){
  121.     int n, m, q; cin >> n >> m >> q;
  122.     vector<vl> lines(n+1, vl(sz, uinf));
  123.     vector<vector<edge>> adj(n+1);
  124.     vi deg(n+5);
  125.     for(int i = 1; i <= m; i++){
  126.         int a; cin >> a;
  127.         adj[a].emplace_back();
  128.         deg[adj[a].back().v]++;
  129.     }
  130.     vl ans(q, LONG_LONG_MAX);
  131.     vector<vector<pll>> queries(n+1);
  132.     for(int i = 0; i < q; i++){
  133.         int l, r, x; cin >> l >> r >> x;
  134.         queries[x].push_back({l, i});
  135.         queries[x].push_back({r, i});
  136.     }
  137.     lines[1][adjust] = 0;
  138.     CHT cht;
  139.     queue<int> order;
  140.     for(int i = 1; i <= n; i++){
  141.         if(deg[i]==0) order.push(i);
  142.     }
  143.     while(!order.empty()){
  144.         int i = order.front(); order.pop();
  145.         cht.init(lines[i], queries[i], ans, i);
  146.         for(auto x: adj[i]){
  147.             for(int k = 0; k < sz; k++){
  148.                 if(lines[i][k]<uinf) lines[x.v][k+x.r] = min(lines[x.v][k+x.r], lines[i][k]+x.cost);
  149.             }
  150.             deg[x.v]--;
  151.             if(!deg[x.v]) order.push(x.v);
  152.         }
  153.         lines[i].clear();
  154.     }
  155.     for(int i = 0; i < q; i++){
  156.         if(ans[i]>=uinf){
  157.             cout << "sorry" << endl;
  158.             continue;
  159.         }
  160.         cout << ans[i] << endl;
  161.     }
  162.  
  163.  
  164.  
  165.  
  166.     return 1;
  167. }
  168.  
  169. int main(){
  170.     ios::sync_with_stdio(false); cin.tie(nullptr);
  171.     int testcase = 1;
  172.     //cin >> testcase;
  173.     for(int tc = 1; tc <= testcase; tc++){
  174.         //cerr << "TESTCASE - " << tc << endl;
  175.         solve();
  176.         //cout << (solve() ? "YES" : "NO") << '\n';
  177.         cerr << endl;
  178.     }
  179.  
  180.     return 0;
  181. }
Success #stdin #stdout #stderr 0s 5324KB
comments (?)
stdin
copy 
3 2 2
1 3 15 1
2 1 0 -1
1 10 3
1 10 2
stdout
copy 
16
sorry
stderr
copy 

    

	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/hnnM74
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
2 hours ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!