oj.uz

Submission #377280

# Submission time Handle Problem Language Result Execution time Memory
377280 2021-03-13T16:51:14 Z YJU Robot (JOI21_ho_t4) C++14
0 / 100
 532 ms 49752 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

map<ll,ll> cnt[N];
ll n,m,x,y,c,p;
ll u[N],dis[N];
vector<pair<ll,pll> > v[N];
priority_queue<pll,vector<pll>,greater<pll> > pq;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,m){
		cin>>x>>y>>c>>p;
		cnt[x][c]+=p;cnt[y][c]+=p;
		v[x].pb(mp(y,mp(c,p)));
		v[y].pb(mp(x,mp(c,p)));
	}
	REP1(i,n){
		u[i]=INF;
		if(SZ(cnt[i])<m)u[i]=0;
		for(auto j:cnt[i])u[i]=min(u[i],j.Y);
	}
	REP1(i,n)dis[i]=INF;
	pq.push(mp(dis[1]=0,1));
	while(SZ(pq)){
		y=pq.top().X,x=pq.top().Y;
		pq.pop();
		if(y>dis[x])continue;
		for(auto i:v[x]){
			ll ec=min(u[x]+i.Y.Y,cnt[x][i.Y.X]-i.Y.Y);
			if(ec+y<dis[i.X]){
				pq.push(mp(dis[i.X]=ec+y,i.X));
			}
		}
	}
	cout<<(dis[n]==INF?-1:dis[n])<<"\n";
	return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14592 KB Output is correct
7 Correct 11 ms 14572 KB Output is correct
8 Correct 10 ms 14572 KB Output is correct
9 Incorrect 12 ms 14828 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 26604 KB Output is correct
2 Correct 57 ms 20424 KB Output is correct
3 Correct 141 ms 30956 KB Output is correct
4 Correct 70 ms 22528 KB Output is correct
5 Incorrect 532 ms 49752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14592 KB Output is correct
7 Correct 11 ms 14572 KB Output is correct
8 Correct 10 ms 14572 KB Output is correct
9 Incorrect 12 ms 14828 KB Output isn't correct
10 Halted 0 ms 0 KB -