oj.uz

Submission #485599

# Submission time Handle Problem Language Result Execution time Memory
485599 2021-11-08T13:31:33 Z PoPularPlusPlus Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 1067464 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

const int N = 100002;
vector<pair<ll,pair<int,ll>>> adj[N];
ll dis[N];

void Dijkstra(ll e){
	 priority_queue< pair<ll,ll>, vector <pair<ll,ll>> , greater<pair<ll,ll>> > pq; 
	 dis[e]=0;
	 pq.push({0,e});
	 while(!pq.empty()){
		 ll node = pq.top().second,ww=pq.top().first;
		 pq.pop();
		 if(dis[node] < ww)continue;
		 for(int i = 0; i < (int)adj[node].size(); i++){
			 int j = i + 1;
			 ll sum = 0 , mx = 0;
			 while(j < (int)adj[node].size() && adj[node][i].vf == adj[node][j].vf){
				 ll w =  adj[node][j].vs.vs;
				 sum += w;
				 mx = max(mx , w);
				 int cur = adj[node][j].vs.vf;
				 if(dis[cur] > dis[node] + w){
					dis[cur] = dis[node] + w;
					pq.push({dis[cur] , cur});
				}
				j++;
			 }
			 if(j == i + 1){
				 if(dis[adj[node][i].vs.vf] > dis[node]){
					 dis[adj[node][i].vs.vf] = dis[node];
					 pq.push({dis[adj[node][i].vs.vf] , adj[node][i].vs.vf});
				 }
			 }
			 else {
				 ll w = adj[node][i].vs.vs;
				 if(dis[adj[node][i].vs.vf] > dis[node] + w){
					 dis[adj[node][i].vs.vf] = dis[node] + w;
					 pq.push({dis[adj[node][i].vs.vf] , adj[node][i].vs.vf});
				 }
				 sum -= mx;
				 for(int k = i; k < j; k++){
					 if(dis[adj[node][k].vs.vf] > dis[node] + sum){
						 pq.push({dis[adj[node][k].vs.vf] , adj[node][k].vs.vf});
					 }
				 }
			 }
			 i = j - 1;
			/* ll w = i.second;
			 if(dis[i.first] > dis[node] + w){
				 dis[i.first] = dis[node] + w;
				 pq.push({dis[i.first],i.first});
			 }*/
		 }
	 }
}

void solve(){
	int n , m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		ll a , b , c , d;
		cin >> a >> b >> c >> d;
		adj[a].pb(mp(c,mp(b,d)));
		adj[b].pb(mp(c,mp(a,d)));
	}
	for(int i = 1; i <= n; i++){
		sort(all(adj[i]));
		dis[i] = 1e18;
	}
	Dijkstra(1);
	cout << (dis[n] >= 1e18 ? -1 : dis[n]) << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2668 KB Output is correct
3 Correct 1 ms 2588 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 10860 KB Output is correct
2 Correct 22 ms 6348 KB Output is correct
3 Correct 86 ms 16232 KB Output is correct
4 Correct 34 ms 8024 KB Output is correct
5 Execution timed out 3096 ms 1067464 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2668 KB Output is correct
3 Correct 1 ms 2588 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 Halted 0 ms 0 KB -