oj.uz

Submission #681783

# Submission time Handle Problem Language Result Execution time Memory
681783 2023-01-14T09:38:15 Z kym Robot (JOI21_ho_t4) C++14
100 / 100
 881 ms 120804 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 200005;
int n,m;
struct edge{
	int a,b,c,p;
};
 
edge E[MAXN];
vector<pi> V[MAXN];
map<int,int> dist[MAXN]; // 1.
int D[MAXN]; // 0. 
map<int,vector<pi>> T[MAXN];
map<int,int> S[MAXN];
struct state {
	int node;
	bool a;// should this be the one left??
	int color; // what colour is the edge that came in?
	bool operator<(const state& o) const { return node < o.node; } 
};
typedef pair<int,state> pis ;
int32_t main() 
{
	IAMSPEED
	cin >> n >> m;
	FOR(i,1,m) {
		cin >> E[i].a >> E[i].b >> E[i].c >> E[i].p;
		V[E[i].a].pb({E[i].b,i});
		V[E[i].b].pb({E[i].a,i});
	}
	FOR(i,1,n) {
 
		for(auto v:V[i]){
			S[i][E[v.s].c]+=E[v.s].p;
			T[i][E[v.s].c].pb(v);
		}
 
	}
	
	std::priority_queue<pis,vector<pis>,greater<pis>> pq;
	memset(D,-1,sizeof D);
	D[1]=0;
	dist[1][0]=0;
	pq.push(make_pair(0, state({1, 0, 0})));
	pq.push(make_pair(0, state({1, 1, 0})));
	while(pq.size()) { // color is jsut the color you CAME INTO THE NODE with
		pis c=pq.top(); pq.pop();
		state ss=c.s;
		int d=c.f;
		int node=ss.node, z=ss.a;
		int color=ss.color;
		if(z==0){
			if(D[node]!=d)continue;
		} else {
			if(dist[node][color] != d)continue;
		}
		
		if(z){ 
			
			if(T[node][color].size()<=1)continue;
			for(auto v:T[node][color]){ // adj list of this color
				if(v.f == node)continue;
				
 
				int sum=S[node][E[v.s].c]; // take everything
 
				int nx=v.f;
				int nd=d + sum - E[v.s].p; // sum - Px (-Pparent is already done at previous node)
				//auto it=dist[nx][0].find(color);

				if(D[nx] == -1 || D[nx]>nd) {
					D[nx]=nd;
					//if(it!=dist[nx][0].end())it->s=nd;
					//else dist[nx][0][color]=nd;
					pq.push(make_pair(nd, state({nx, 0, color}))); // don't make the other node choose everything
				}
				
				
			}
		} else {
			for(auto v:V[node]) {
				int nx=v.f;
 
				int nd=d;
				int thiscolor=E[v.s].c;
				bool changed=0;
				if(T[node][thiscolor].size()>1) {
					nd += E[v.s].p;
					changed=1;
				}
				
				
				
				if(D[nx] == -1 || D[nx]>min(nd, d + S[node][E[v.s].c] - E[v.s].p)) {
					D[nx]=min(nd, d + S[node][E[v.s].c] - E[v.s].p);
					
					pq.push(make_pair(min(nd, d + S[node][E[v.s].c] - E[v.s].p), state({nx, 0, thiscolor}))); // don't make the other node choose everything
				}
				if(changed){ 
					auto it2=dist[nx].find(thiscolor);
					if(it2 == dist[nx].end() || it2->s>nd-E[v.s].p) {
						if(it2!=dist[nx].end())it2->s=nd-E[v.s].p;
						else dist[nx][thiscolor]=nd-E[v.s].p;
						pq.push(make_pair(nd-E[v.s].p, state({nx, 1, thiscolor})));//yes you must choose everything to get this compensation
					}
				}
 
				
				
			}
		}
	}
	cout << D[n];
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 34700 KB Output is correct
2 Correct 20 ms 34776 KB Output is correct
3 Correct 18 ms 34788 KB Output is correct
4 Correct 16 ms 34740 KB Output is correct
5 Correct 17 ms 34820 KB Output is correct
6 Correct 17 ms 34780 KB Output is correct
7 Correct 18 ms 34948 KB Output is correct
8 Correct 15 ms 34772 KB Output is correct
9 Correct 22 ms 35548 KB Output is correct
10 Correct 19 ms 35396 KB Output is correct
11 Correct 19 ms 35156 KB Output is correct
12 Correct 25 ms 35196 KB Output is correct
13 Correct 20 ms 35284 KB Output is correct
14 Correct 19 ms 35284 KB Output is correct
15 Correct 21 ms 35020 KB Output is correct
16 Correct 21 ms 35220 KB Output is correct
17 Correct 20 ms 35156 KB Output is correct
18 Correct 17 ms 34892 KB Output is correct
19 Correct 21 ms 35132 KB Output is correct
20 Correct 19 ms 35124 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 59300 KB Output is correct
2 Correct 94 ms 46900 KB Output is correct
3 Correct 164 ms 59792 KB Output is correct
4 Correct 110 ms 51024 KB Output is correct
5 Correct 831 ms 114244 KB Output is correct
6 Correct 675 ms 106516 KB Output is correct
7 Correct 330 ms 87744 KB Output is correct
8 Correct 322 ms 84616 KB Output is correct
9 Correct 369 ms 84548 KB Output is correct
10 Correct 254 ms 76772 KB Output is correct
11 Correct 105 ms 59640 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 34700 KB Output is correct
2 Correct 20 ms 34776 KB Output is correct
3 Correct 18 ms 34788 KB Output is correct
4 Correct 16 ms 34740 KB Output is correct
5 Correct 17 ms 34820 KB Output is correct
6 Correct 17 ms 34780 KB Output is correct
7 Correct 18 ms 34948 KB Output is correct
8 Correct 15 ms 34772 KB Output is correct
9 Correct 22 ms 35548 KB Output is correct
10 Correct 19 ms 35396 KB Output is correct
11 Correct 19 ms 35156 KB Output is correct
12 Correct 25 ms 35196 KB Output is correct
13 Correct 20 ms 35284 KB Output is correct
14 Correct 19 ms 35284 KB Output is correct
15 Correct 21 ms 35020 KB Output is correct
16 Correct 21 ms 35220 KB Output is correct
17 Correct 20 ms 35156 KB Output is correct
18 Correct 17 ms 34892 KB Output is correct
19 Correct 21 ms 35132 KB Output is correct
20 Correct 19 ms 35124 KB Output is correct
21 Correct 183 ms 59300 KB Output is correct
22 Correct 94 ms 46900 KB Output is correct
23 Correct 164 ms 59792 KB Output is correct
24 Correct 110 ms 51024 KB Output is correct
25 Correct 831 ms 114244 KB Output is correct
26 Correct 675 ms 106516 KB Output is correct
27 Correct 330 ms 87744 KB Output is correct
28 Correct 322 ms 84616 KB Output is correct
29 Correct 369 ms 84548 KB Output is correct
30 Correct 254 ms 76772 KB Output is correct
31 Correct 105 ms 59640 KB Output is correct
32 Correct 133 ms 58572 KB Output is correct
33 Correct 159 ms 59696 KB Output is correct
34 Correct 335 ms 81284 KB Output is correct
35 Correct 317 ms 70736 KB Output is correct
36 Correct 256 ms 75140 KB Output is correct
37 Correct 340 ms 80740 KB Output is correct
38 Correct 325 ms 96512 KB Output is correct
39 Correct 159 ms 65696 KB Output is correct
40 Correct 338 ms 85920 KB Output is correct
41 Correct 411 ms 86256 KB Output is correct
42 Correct 393 ms 94424 KB Output is correct
43 Correct 187 ms 64392 KB Output is correct
44 Correct 326 ms 78228 KB Output is correct
45 Correct 310 ms 78480 KB Output is correct
46 Correct 242 ms 76832 KB Output is correct
47 Correct 267 ms 79304 KB Output is correct
48 Correct 881 ms 120804 KB Output is correct