oj.uz

Submission #939449

# Submission time Handle Problem Language Result Execution time Memory
939449 2024-03-06T11:24:36 Z koukirocks Robot (JOI21_ho_t4) C++17
34 / 100
 260 ms 119216 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

ll n,m;

struct edge{
	ll des,clr,cst;
	edge(ll _des,ll _clr,ll _cst):des(_des),clr(_clr),cst(_cst){}
};

vector<edge> G[MAX];
vector<pll> G2[MAX*3];

int main() {
	speed;
	cin>>n>>m;
	for (int i=0;i<m;i++) {
		ll a,b,c,p;
		cin>>a>>b>>c>>p;
		G[a].emplace_back(b,c,p);
		G[b].emplace_back(a,c,p);
		G2[a].emplace_back(b,p);
		G2[b].emplace_back(a,p);
	}
	ll now=n+1;
	for (int i=1;i<=n;i++) {
		map<int,vector<pll> > ttl;
		for (auto eg:G[i]) ttl[eg.clr].emplace_back(eg.des,eg.cst);
		for (auto [clr,egs]:ttl) {
			ll ttlw=0;
			for (auto eg:egs) ttlw+=eg.second;
			G2[i].push_back({now,0});
			for (auto eg:egs) {
				G2[now].emplace_back(eg.first,ttlw-eg.second);
				G2[eg.first].emplace_back(now,0);
			}
//			cout<<i<<" "<<clr<<" "<<now<<"\n";
			now++;
		}
	}
//	for (int i=1;i<now;i++) {
//		cout<<i<<".\n";
//		for (auto j:G2[i]) {
//			cout<<j.first<<" "<<j.second<<"\n";
//		}
//		cout<<"----\n";
//	}
	priority_queue<pll> D;
	vector<bool> vis(now+1,0);
	vector<ll> dis(now+1,oo);
	dis[1]=0;
	D.emplace(0,1);
	while (!D.empty()) {
		while (!D.empty() and vis[D.top().second]) D.pop();
		if (D.empty()) break;
		int v=D.top().second;
		D.pop();
		vis[v]=true;
		for (auto [u,w]:G2[v]) {
			if (!vis[u] and dis[v]+w<dis[u]) {
				dis[u]=dis[v]+w;
				D.emplace(-dis[u],u);
			}
		}
	}
	cout<<(dis[n]==oo?-1:dis[n])<<"\n";
	return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9816 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 5 ms 10332 KB Output is correct
10 Correct 4 ms 10332 KB Output is correct
11 Correct 4 ms 10332 KB Output is correct
12 Correct 4 ms 10332 KB Output is correct
13 Correct 6 ms 10332 KB Output is correct
14 Correct 5 ms 10332 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 4 ms 10376 KB Output is correct
17 Correct 4 ms 10076 KB Output is correct
18 Correct 3 ms 9820 KB Output is correct
19 Correct 4 ms 10320 KB Output is correct
20 Correct 3 ms 10076 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 29904 KB Output is correct
2 Correct 46 ms 18824 KB Output is correct
3 Correct 108 ms 40668 KB Output is correct
4 Correct 61 ms 22736 KB Output is correct
5 Runtime error 260 ms 119216 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9816 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 5 ms 10332 KB Output is correct
10 Correct 4 ms 10332 KB Output is correct
11 Correct 4 ms 10332 KB Output is correct
12 Correct 4 ms 10332 KB Output is correct
13 Correct 6 ms 10332 KB Output is correct
14 Correct 5 ms 10332 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 4 ms 10376 KB Output is correct
17 Correct 4 ms 10076 KB Output is correct
18 Correct 3 ms 9820 KB Output is correct
19 Correct 4 ms 10320 KB Output is correct
20 Correct 3 ms 10076 KB Output is correct
21 Correct 96 ms 29904 KB Output is correct
22 Correct 46 ms 18824 KB Output is correct
23 Correct 108 ms 40668 KB Output is correct
24 Correct 61 ms 22736 KB Output is correct
25 Runtime error 260 ms 119216 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -