oj.uz

Submission #760388

# Submission time Handle Problem Language Result Execution time Memory
760388 2023-06-17T14:26:25 Z shadow_sami Toll (BOI17_toll) C++17
10 / 100
 62 ms 11876 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});
		}
		fip(0,n+2)
				dis[i] = 1e18;
			emptify();
			pq.push({0,0});
			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});
				}
			}
		while(tp2--){
			cin>>sr>>de;
			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 Incorrect 17 ms 5448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7144 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 1 ms 2680 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct
9 Correct 19 ms 6328 KB Output is correct
10 Correct 62 ms 11876 KB Output is correct
11 Correct 39 ms 8600 KB Output is correct
12 Correct 22 ms 7696 KB Output is correct
13 Correct 62 ms 11824 KB Output is correct
14 Correct 28 ms 8260 KB Output is correct
15 Correct 24 ms 7656 KB Output is correct
16 Correct 24 ms 7692 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 5448 KB Output isn't correct
2 Halted 0 ms 0 KB -