oj.uz

Submission #976212

# Submission time Handle Problem Language Result Execution time Memory
976212 2024-05-06T09:49:10 Z hocln Cyberland (APIO23_cyberland) C++17
44 / 100
 33 ms 11604 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "cyberland.h"
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
//const long long MOD = 1e9 + 7;
const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
int tc = 0;
const int N = 1e5 + 15;
vector<pll>adj[N];
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int>c, vector<int>a) {
	for(int i = 0;i < n;i++) adj[i].clear();
	for(int i = 0;i < m;i++) {
		adj[x[i]].emplace_back(y[i],c[i]);
		adj[y[i]].emplace_back(x[i],c[i]);
	}
	priority_queue<pll>q;
	q.emplace(0,0);
	vector<ll>dist(n,INF);
	dist[0] = 0;
	while(!q.empty()) {
		int node = q.top().second;
		q.pop();
		if(node == h) continue;
		for(auto& i : adj[node]) {
			if(chmin(dist[i.first], dist[node] + i.second)) q.emplace(-dist[i.first],i.first);
		}
	}
	vector<ll>d2(n,INF);
	q.emplace(0,h);
	d2[h] = 0;
	while(!q.empty()) {
		int node = q.top().second;
		q.pop();
		for(auto& i : adj[node]) {
			if(chmin(d2[i.first], d2[node] + i.second)) q.emplace(-d2[i.first],i.first);
		}
	}
	ll ans = dist[h];
	if(ans == INF) return -1;
	for(int i = 0;i < n;i++) {
		if(dist[i] != INF && a[i] == 0) chmin(ans, d2[i]);
	}
	//debug()<<imie(dist)imie(d2);
	return ans;
}
//inline void solve_test() {
	
//}

//int main()
//{
    ////srand(chrono::steady_clock::now().time_since_epoch().count());
    ////freopen("convention2.in", "r", stdin);
    ////freopen("convention2.out", "w", stdout);
	////cout << "Case #" << tc << ": " << ans << '\n';
	////cout << fixed << setprecision(7);
    ////ios::sync_with_stdio(0);
    ////cin.tie(0);cout.tie(0);
    ////int tt = 1;
    //////cin >> tt;
    ////while(tt--) {
		////++tc;
        ////solve_test();
    ////}
    //cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
//}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 2904 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2904 KB Correct.
2 Correct 24 ms 2968 KB Correct.
3 Correct 21 ms 2904 KB Correct.
4 Correct 22 ms 2908 KB Correct.
5 Correct 22 ms 2908 KB Correct.
6 Correct 21 ms 3932 KB Correct.
7 Correct 25 ms 3676 KB Correct.
8 Correct 12 ms 4700 KB Correct.
9 Correct 20 ms 2880 KB Correct.
10 Correct 20 ms 2652 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2908 KB Correct.
2 Correct 22 ms 3676 KB Correct.
3 Correct 20 ms 3728 KB Correct.
4 Correct 21 ms 3676 KB Correct.
5 Correct 26 ms 3420 KB Correct.
6 Correct 5 ms 3672 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8284 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2904 KB Correct.
2 Correct 21 ms 2908 KB Correct.
3 Correct 21 ms 2908 KB Correct.
4 Correct 20 ms 4084 KB Correct.
5 Correct 17 ms 2648 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2908 KB Correct.
2 Correct 17 ms 3888 KB Correct.
3 Correct 33 ms 11604 KB Correct.
4 Correct 14 ms 4416 KB Correct.
5 Correct 19 ms 3676 KB Correct.
6 Correct 19 ms 3676 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2908 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2908 KB Wrong Answer.
2 Halted 0 ms 0 KB -