oj.uz

Submission #416302

# Submission time Handle Problem Language Result Execution time Memory
416302 2021-06-02T09:37:59 Z alishahali1382 Robot (JOI21_ho_t4) C++14
34 / 100
 3000 ms 88300 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, int> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=800010, LOG=20;

int n, m, k, u, v, x, y, t, a, b;
int A[MAXN], B[MAXN], C[MAXN], P[MAXN];
ll P2[MAXN], sum[MAXN];
ll dist[MAXN], ans;
bool mark[MAXN];
int col[MAXN], mark2[MAXN];
vector<int> G[MAXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;
map<int, bool> mp[MAXN]; 

inline void upd(int v, ll d){ if (dist[v]>d) pq.push({dist[v]=d, v});}
inline bool cmp(int i, int j){ return C[i]<C[j];}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=0; i<2*m; i++){
		cin>>u>>v>>x>>y;
		A[i]=u, B[i]=v, C[i]=x, P[i]=y, G[u].pb(i);
		swap(u, v);
		i++;
		A[i]=u, B[i]=v, C[i]=x, P[i]=y, G[u].pb(i);
	}
	for (int i=1; i<=n; i++){
		for (int j:G[i]) sum[C[j]]=0;
		for (int j:G[i]) sum[C[j]]+=P[j];
		for (int j:G[i]) P2[j]+=sum[C[j]];
	}
	memset(dist, 63, sizeof(dist));
	for (int i:G[1]){
		upd(i<<1, P2[i]-P[i]);
		upd(i<<1 | 1, P[i]);
	}
	ans=INF;
	while (pq.size()){
		int st=pq.top().second;
		pq.pop();
		if (mark[st]) continue ;
		mark[st]=1;
		int id=(st>>1), last=(st&1);
		int v=B[id];
		if (v==n) kill(dist[st]);
		if (!mark2[v]){
			mark2[v]=1;
			for (int i:G[v]){
				upd(i<<1 | 1, dist[st]+P[i]);
				if (C[id]!=C[i]) upd(i<<1, dist[st]+P2[i]-P[i]);
				else if (last) upd(i<<1, dist[st]+P2[i]-P[i]-P[id]);
			}
			col[v]=C[id];
		}
		else if (last && mp[v][C[id]]++<2){
			for (int i:G[v]){
				if (C[id]==C[i]) upd(i<<1, dist[st]+P2[i]-P[i]-P[id]);
			}
		}
		
	}
	if (ans>=INF) ans=-1;
	cout<<ans<<"\n";
	
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:78:32: warning: use of an operand of type 'bool' in 'operator++' is deprecated [-Wdeprecated]
   78 |   else if (last && mp[v][C[id]]++<2){
      |                                ^~
Main.cpp:78:34: warning: comparison of constant '2' with boolean expression is always true [-Wbool-compare]
   78 |   else if (last && mp[v][C[id]]++<2){

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 63012 KB Output is correct
2 Correct 36 ms 62996 KB Output is correct
3 Correct 38 ms 63052 KB Output is correct
4 Correct 36 ms 62864 KB Output is correct
5 Correct 35 ms 63012 KB Output is correct
6 Correct 35 ms 62924 KB Output is correct
7 Correct 35 ms 63244 KB Output is correct
8 Correct 35 ms 62960 KB Output is correct
9 Correct 42 ms 63328 KB Output is correct
10 Correct 47 ms 63292 KB Output is correct
11 Correct 44 ms 63376 KB Output is correct
12 Correct 42 ms 63216 KB Output is correct
13 Correct 51 ms 63316 KB Output is correct
14 Correct 46 ms 63300 KB Output is correct
15 Correct 37 ms 62992 KB Output is correct
16 Correct 39 ms 63180 KB Output is correct
17 Correct 38 ms 63240 KB Output is correct
18 Correct 40 ms 62956 KB Output is correct
19 Correct 40 ms 63300 KB Output is correct
20 Correct 39 ms 63076 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 73016 KB Output is correct
2 Correct 109 ms 68012 KB Output is correct
3 Correct 118 ms 72264 KB Output is correct
4 Correct 81 ms 68032 KB Output is correct
5 Execution timed out 3077 ms 88300 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 63012 KB Output is correct
2 Correct 36 ms 62996 KB Output is correct
3 Correct 38 ms 63052 KB Output is correct
4 Correct 36 ms 62864 KB Output is correct
5 Correct 35 ms 63012 KB Output is correct
6 Correct 35 ms 62924 KB Output is correct
7 Correct 35 ms 63244 KB Output is correct
8 Correct 35 ms 62960 KB Output is correct
9 Correct 42 ms 63328 KB Output is correct
10 Correct 47 ms 63292 KB Output is correct
11 Correct 44 ms 63376 KB Output is correct
12 Correct 42 ms 63216 KB Output is correct
13 Correct 51 ms 63316 KB Output is correct
14 Correct 46 ms 63300 KB Output is correct
15 Correct 37 ms 62992 KB Output is correct
16 Correct 39 ms 63180 KB Output is correct
17 Correct 38 ms 63240 KB Output is correct
18 Correct 40 ms 62956 KB Output is correct
19 Correct 40 ms 63300 KB Output is correct
20 Correct 39 ms 63076 KB Output is correct
21 Correct 170 ms 73016 KB Output is correct
22 Correct 109 ms 68012 KB Output is correct
23 Correct 118 ms 72264 KB Output is correct
24 Correct 81 ms 68032 KB Output is correct
25 Execution timed out 3077 ms 88300 KB Time limit exceeded
26 Halted 0 ms 0 KB -