oj.uz

Submission #760386

# Submission time Handle Problem Language Result Execution time Memory
760386 2023-06-17T14:24:16 Z shadow_sami Toll (BOI17_toll) C++17
8 / 100
 3000 ms 11708 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
#define ff first
#define ss second
#define fip(a,b) for(ll i = a ; i < b ; i++)
#define fjp(a,b) for(ll j = a ; j < b ; j++)
#define fp(x,a,b) for(ll x = a ; x < b ; x++)
#define fin(a,b) for(ll i = a : i >= b; i--)
#define fjn(a,b) for(ll j = a : j >= b; j--)
#define fn(x,a,b) for(ll x  = a ; x >= b ; x--);
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define total_one(a) __builtin_popcount(a)
#define front_zero(a) __builtin_clzll(a)
#define back_zero(a) __builtin_ctzll(a)
#define fx(a) for(auto x : a)
#define nli "\n"

#if ONLINE_JUDGE
#define	debug(x) cerr<< #x <<" "<< printn(n) << nli;
#else
#define debug(x)
#endif

void printn(ll a){ cerr<<a<<" ";}
void printn(int a){ cerr<<a<<" ";}
template <class T,class V> void _printn(pair<T,V> a){ cerr<<"( "<<a.ff<<" , "<<a.ss<<" ) "<<nli;}
template <class T> void _printn(vector<T> a){ 
	cerr<<"[ ";
	for(auto x : a){
		_printn(a);
		cerr<<nli;
	}
	cerr<<"]"<<nli;
	return;
}

const ll mx =  1e5+5;

ll n,m,k,q,tp,tp2,res,sum,tptp,cnt,ans;
bool f = false;
vector<pi> ve;
vector<pi> adj[mx];
ll dis[mx];

priority_queue<pi,vector<pi>,greater<pi>> pq;

void emptify(){
	while(pq.size())
		pq.pop();
	return;
}

int sr,de;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	// #ifndef ONLINE_JUDGE
	// 	freopen("input1.txt","r",stdin);
	// 	freopen("output1.txt","w",stdout);
	// 	freopen("error1.txt","w",stderr);
	// #endif

		cin>>k>>n>>m>>tp2;
		fip(0,m){
			cin>>sr>>de>>tp;
			ve.push_back({sr,de});
			adj[sr].push_back({de,tp});
		}
		while(tp2--){
			cin>>sr>>de;
			fip(0,n+2)
				dis[i] = 1e18;
			emptify();
			pq.push({0,sr});
			while(pq.size()){
				auto it = pq.top();
				pq.pop();
				if(dis[it.ss] < it.ff)
					continue;
				dis[it.ss] = it.ff;
				fx(adj[it.ss]){
					if(dis[x.ff] > dis[it.ss] + x.ss)
						pq.push({dis[it.ss] + x.ss,x.ff});
				}
			}
			if(dis[de]>1e9)
				dis[de] = -1;
			cout<<dis[de]<<nli;
		}

	cerr << "time elapsed : " <<setprecision(6)<< clock()  * 1000.00 / CLOCKS_PER_SEC << " ms"<<nli;
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 6312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 8196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 4 ms 2776 KB Output is correct
8 Correct 19 ms 2972 KB Output is correct
9 Correct 13 ms 2848 KB Output is correct
10 Correct 18 ms 6192 KB Output is correct
11 Correct 381 ms 8244 KB Output is correct
12 Correct 524 ms 11708 KB Output is correct
13 Correct 990 ms 11708 KB Output is correct
14 Correct 808 ms 9180 KB Output is correct
15 Correct 408 ms 7604 KB Output is correct
16 Correct 257 ms 7532 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 4 ms 2776 KB Output is correct
8 Correct 19 ms 2972 KB Output is correct
9 Correct 13 ms 2848 KB Output is correct
10 Correct 18 ms 6192 KB Output is correct
11 Correct 381 ms 8244 KB Output is correct
12 Correct 524 ms 11708 KB Output is correct
13 Correct 990 ms 11708 KB Output is correct
14 Correct 808 ms 9180 KB Output is correct
15 Correct 408 ms 7604 KB Output is correct
16 Correct 257 ms 7532 KB Output is correct
17 Execution timed out 3017 ms 8260 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 6312 KB Time limit exceeded
2 Halted 0 ms 0 KB -