oj.uz

Submission #768823

# Submission time Handle Problem Language Result Execution time Memory
768823 2023-06-28T17:26:57 Z LeoChen112358 Robot (JOI21_ho_t4) C++14
34 / 100
 3000 ms 1079580 KB 
#include <bits/stdc++.h>
using namespace std;

const int Nlim=1e5,Mlim=2e5,Vlim=1e9;
const long INF=(long)Vlim*Mlim+1;
#define pii pair<long,pair<int,int>>
int N,M;
struct edge{
	int node,color,price;
	edge(int nn,int cc,int pp){
		node=nn;
		color=cc;
		price=pp;
	}
};
map<int,vector<edge>>conn[Nlim];
//cost = min(recolor you, recolor neighbors)
//cost to get to i
long dp1[Nlim];
//cost to get to i with a c-edge and will go thru another c-edge (so we'll recolor later)
//applies only when we are to recolor neighbors originally (gets affected)
map<int,long>dp2[Nlim],sum[Nlim];

int main(){
	cin>>N>>M;
	for(int i=0; i<M; i++){
		int a,b,c,p;
		cin>>a>>b>>c>>p;
		a--,b--,c--;
		conn[a][c].push_back(edge(b,c,p));
		conn[b][c].push_back(edge(a,c,p));//undirected
		sum[a][c]+=p;
		sum[b][c]+=p;
	}
	for(int i=0; i<N; i++){
		dp1[i]=INF;
		for(int j=0; j<M; j++)dp2[i][j]=INF;
	}
	priority_queue<pii,vector<pii>,greater<pii>>PQ;
	PQ.push({0,{0,-1}});//cost,node,color
	dp1[0]=0;
	while(!PQ.empty()){
		long prc=PQ.top().first,node=PQ.top().second.first,col=PQ.top().second.second;
		PQ.pop();
		if(col==-1){//no need to recolor neighbor stuff (normal way)
			if(dp1[node]!=prc)continue;
			for(auto stuff:conn[node]){//each color
				for(auto i:stuff.second){
					//1. recolor this edge
					long v1=prc+i.price;
					if(v1<dp1[i.node]){
						dp1[i.node]=v1;
						PQ.push({dp1[i.node],{i.node,-1}});
					}
					//2. recolor neighbors
					long v2=prc+sum[node][i.color]-i.price;
					if(v2<dp1[i.node]){
						dp1[i.node]=v2;
						PQ.push({dp1[i.node],{i.node,-1}});
					}
					//3. recolor at next step (virtual transition)
					if(dp2[i.node].count(i.color)==0 or prc<dp2[i.node][i.color]){
						dp2[i.node][i.color]=prc;
						PQ.push({prc,{i.node,i.color}});
					}
				}
			}
		}
		else{//need to recolor neighbor stuff (special case)
			if(dp2[node][col]!=prc)continue;
			for(auto i:conn[node][col]){
				long val=sum[node][col];
				if(prc+val-i.price<dp1[i.node]){
					dp1[i.node]=prc+val-i.price;
					PQ.push({dp1[i.node],{i.node,-1}});
				}
			}
		}
	}
	if(dp1[N-1]==INF)cout<<-1<<'\n';
	else cout<<dp1[N-1]<<'\n';
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14300 KB Output is correct
3 Correct 9 ms 14404 KB Output is correct
4 Correct 9 ms 14292 KB Output is correct
5 Correct 8 ms 14804 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 14 ms 18036 KB Output is correct
8 Correct 9 ms 15956 KB Output is correct
9 Correct 213 ms 139156 KB Output is correct
10 Correct 214 ms 139212 KB Output is correct
11 Correct 216 ms 139272 KB Output is correct
12 Correct 164 ms 118220 KB Output is correct
13 Correct 227 ms 138936 KB Output is correct
14 Correct 219 ms 138828 KB Output is correct
15 Correct 108 ms 77056 KB Output is correct
16 Correct 202 ms 139720 KB Output is correct
17 Correct 119 ms 88692 KB Output is correct
18 Correct 56 ms 47308 KB Output is correct
19 Correct 33 ms 27004 KB Output is correct
20 Correct 140 ms 98036 KB Output is correct

Subtask #2
0 / 24.0

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

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14300 KB Output is correct
3 Correct 9 ms 14404 KB Output is correct
4 Correct 9 ms 14292 KB Output is correct
5 Correct 8 ms 14804 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 14 ms 18036 KB Output is correct
8 Correct 9 ms 15956 KB Output is correct
9 Correct 213 ms 139156 KB Output is correct
10 Correct 214 ms 139212 KB Output is correct
11 Correct 216 ms 139272 KB Output is correct
12 Correct 164 ms 118220 KB Output is correct
13 Correct 227 ms 138936 KB Output is correct
14 Correct 219 ms 138828 KB Output is correct
15 Correct 108 ms 77056 KB Output is correct
16 Correct 202 ms 139720 KB Output is correct
17 Correct 119 ms 88692 KB Output is correct
18 Correct 56 ms 47308 KB Output is correct
19 Correct 33 ms 27004 KB Output is correct
20 Correct 140 ms 98036 KB Output is correct
21 Execution timed out 3121 ms 1079580 KB Time limit exceeded
22 Halted 0 ms 0 KB -