oj.uz

Submission #412995

# Submission time Handle Problem Language Result Execution time Memory
412995 2021-05-28T00:53:09 Z Chaska Robot (JOI21_ho_t4) C++11
0 / 100
 1845 ms 101140 KB 
#include <bits/stdc++.h> 
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())
#define PI 3.141592
#define fo(i,n) for (int i=0;i<n;i++)
#define fofo(i,n,j,m) for (int i=0;i<n;i++) for (int j=0;j<m;j++) 
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int N=1e5+5,M=2e5+5,mod=1e9+7;

ll n,m;
map<ll,ll> h[N];
map<ll,ll> hp[N];
vector<ll> g[N];
map<ii,ll> pr;
map<ii,ll> co;
bool vs[N];
ll res[N];
priority_queue<ii,vector<ii>,greater<ii>> pq;
void dij(ll cost,ll node)
{
	if (vs[node]) return;
	vs[node] = true;
	res[node] = cost;
	for (int u : g[node]) {
		if (!vs[u] && h[node][co[{node,u}]]==1) {
			pq.push({cost,u});
			//dij(u,cost);
		}
	}
	for (int u : g[node]) {
		if (!vs[u]) if (h[node][co[{node,u}]]>1) {
			pq.push({cost+min(pr[{node,u}],hp[node][co[{node,u}]]-pr[{node,u}]),u});
			//dij(u,cost);
		}
	}
}

int main() { 
	cin.tie(0); cout.tie(0); 
	ios_base::sync_with_stdio();
	cin >> n >> m;
	for (int i=0;i<m;i++) {
		ll a,b,c,p;
		cin >> a >> b >> c >> p;
		co[{a,b}] = c;
		co[{b,a}] = c;
		pr[{a,b}] = p;
		pr[{b,a}] = p;
		g[a].push_back(b);
		g[b].push_back(a);
		h[a][c]++;
		hp[a][c] += p;
		h[b][c]++;
		hp[b][c] += p;
	}
	pq.push({0,1});
	while (!pq.empty()) {
		auto x = pq.top();
		pq.pop();
		dij(x.fi,x.se);
	}
	if (!vs[n]) cout << -1;
	else cout << res[n];
	return 0;
}

// Recuerda limites 
// Recuerda casos especiales

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 7 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 11980 KB Output is correct
7 Correct 10 ms 12364 KB Output is correct
8 Correct 8 ms 12108 KB Output is correct
9 Incorrect 13 ms 12960 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 43864 KB Output is correct
2 Correct 190 ms 26820 KB Output is correct
3 Correct 892 ms 55800 KB Output is correct
4 Correct 299 ms 33052 KB Output is correct
5 Incorrect 1845 ms 101140 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 7 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 11980 KB Output is correct
7 Correct 10 ms 12364 KB Output is correct
8 Correct 8 ms 12108 KB Output is correct
9 Incorrect 13 ms 12960 KB Output isn't correct
10 Halted 0 ms 0 KB -