oj.uz

Submission #416346

# Submission time Handle Problem Language Result Execution time Memory
416346 2021-06-02T10:34:02 Z alishahali1382 Robot (JOI21_ho_t4) C++14
24 / 100
 1080 ms 101368 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];
int fuck[MAXN];
vector<int> G[MAXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;
map<int, ll> 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];}
inline bool cmp2(int i, int j){
	if (C[i]!=C[j]) return C[i]<C[j];
	return P[i]>P[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++){
		sort(all(G[i]), cmp);
		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;
	int shit=0;
	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].count(C[id]) || mp[v][C[id]]>dist[st]-P[id])){
			mp[v][C[id]]=dist[st]-P[id];
			auto it=lower_bound(all(G[v]), id, cmp);
			while (it!=G[v].end() && C[*it]==C[id]){	
				int i=*(it++);
				if (P2[i]-P[i]-P[id]>=P[i]) break ;
				upd(i<<1, dist[st]+P2[i]-P[i]-P[id]);
			}
		}
	}
	cout<<"-1\n";
	
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:68:6: warning: unused variable 'shit' [-Wunused-variable]
   68 |  int shit=0;
      |      ^~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62916 KB Output is correct
2 Correct 42 ms 62888 KB Output is correct
3 Correct 46 ms 62900 KB Output is correct
4 Correct 42 ms 62980 KB Output is correct
5 Correct 39 ms 62916 KB Output is correct
6 Correct 39 ms 62948 KB Output is correct
7 Correct 40 ms 63128 KB Output is correct
8 Correct 41 ms 62992 KB Output is correct
9 Correct 41 ms 63312 KB Output is correct
10 Correct 41 ms 63384 KB Output is correct
11 Correct 40 ms 63172 KB Output is correct
12 Incorrect 39 ms 63148 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 73124 KB Output is correct
2 Correct 114 ms 68440 KB Output is correct
3 Correct 125 ms 72192 KB Output is correct
4 Correct 83 ms 68048 KB Output is correct
5 Correct 1080 ms 101368 KB Output is correct
6 Correct 889 ms 97052 KB Output is correct
7 Correct 369 ms 85268 KB Output is correct
8 Correct 445 ms 84396 KB Output is correct
9 Correct 508 ms 84344 KB Output is correct
10 Correct 370 ms 80184 KB Output is correct
11 Correct 117 ms 71012 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62916 KB Output is correct
2 Correct 42 ms 62888 KB Output is correct
3 Correct 46 ms 62900 KB Output is correct
4 Correct 42 ms 62980 KB Output is correct
5 Correct 39 ms 62916 KB Output is correct
6 Correct 39 ms 62948 KB Output is correct
7 Correct 40 ms 63128 KB Output is correct
8 Correct 41 ms 62992 KB Output is correct
9 Correct 41 ms 63312 KB Output is correct
10 Correct 41 ms 63384 KB Output is correct
11 Correct 40 ms 63172 KB Output is correct
12 Incorrect 39 ms 63148 KB Output isn't correct
13 Halted 0 ms 0 KB -