oj.uz

Submission #749352

# Submission time Handle Problem Language Result Execution time Memory
749352 2023-05-27T19:35:57 Z shadow_sami Cyberland (APIO23_cyberland) C++17
100 / 100
 287 ms 100168 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans,q,k;
const ll mx = 2e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
vector<pi> adj[mx];
double dis[mx][105];
vector<int> node;
bool vis[mx];
double rip[105];
priority_queue<pair<double,pi>,vector<pair<double,pi>>,greater<pair<double,pi>>> pq;

typedef struct Disjoint_Set_Union{
	ll parent[mx];
	ll siz[mx];
	ll src;ll dest;
	void init(ll k){
		fip(0,k+2){
			parent[i] = i;
			siz[i] = 1;
		}
	}
	ll find(ll u){
		return parent[u] == u ? u : parent[u] = find(parent[u]);
	}
	bool unite(ll u,ll v){
		src = find(u);
		dest = find(v);
		if(src==dest)
			return 1;
		if(siz[src] < siz[dest]) 
			swap(src,dest);
		parent[dest] = src;
		siz[src] += siz[dest];
		return  0;
	}
}DSU;

DSU dsu;

void dfs(ll u){
	vis[u] = 1;
	if(u==tp){
		f = 0;
		return ;
	}		
	fx(adj[u])		{
		if(!vis[x.ff])
			dfs(x.ff);
	}
	return;
}

void emptify(){
	while(pq.size()){
		pq.pop();
	}
	return;
}

void printer(){
	priority_queue<pair<double,pi>,vector<pair<double,pi>>,greater<pair<double,pi>>> pq2 = pq;
	cout<<"start - > ";
	while(pq2.size()){
		debug(pq2.top());
		pq2.pop();
	}
	cout<<" end."<<nli;
	return;
}

double solve(int N, int M, int K, int H,vector<int> x, vector<int> y, vector<int> c,vector<int> arr) {
	n = N;m = M;
	tp = H;
	node.clear();
	dsu.init(n);
	k = min(100,K);
	rip[0] = 1;
	fip(1,k+1)
		rip[i] = rip[i-1] / 2;
	node = arr;
	fip(0,n+2){
		adj[i].clear();
		fjp(0,105)
			dis[i][j] = 1e18+5;
		vis[i] = 0;
	}
	emptify();
	fip(0,m){
		if(x[i] != tp && tp != y[i])
			dsu.unite(x[i],y[i]);
		adj[x[i]].push_back({y[i],c[i]});
		adj[y[i]].push_back({x[i],c[i]});
	}
	f = 1;
	node[0] = 0;
	dfs(0);
	if(f)
		return -1;
    pq.push({0,{tp,k}});
    double na = -1;
    cout<<setprecision(6);
    dis[tp][k] = 0;
    while(pq.size()){
    	auto it = pq.top();
    	pq.pop();
    	if(dis[it.ss.ff][it.ss.ss] < it.ff)
    		continue;
    	if(node[it.ss.ff]==0){
    		na = it.ff;
    		break;
    	}
    	fx(adj[it.ss.ff]){
    		if(dsu.find(0) != dsu.find(x.ff))
    			continue;
    		if(it.ff + x.ss * rip[k-it.ss.ss] < dis[x.ff][it.ss.ss]){
    			dis[x.ff][it.ss.ss] = it.ff + x.ss * rip[k-it.ss.ss];
    			pq.push({dis[x.ff][it.ss.ss],{x.ff,it.ss.ss}});
    		}
    		if(node[it.ss.ff] == 2 && it.ss.ss >= 1){
    			if(it.ff + x.ss * rip[k-it.ss.ss+1] < dis[x.ff][it.ss.ss-1]){
	    			dis[x.ff][it.ss.ss-1] = it.ff + x.ss * rip[k-it.ss.ss+1];
	    			pq.push({dis[x.ff][it.ss.ss-1],{x.ff,it.ss.ss-1}});
	    		}	
    		}    			
    	}
    }
    return na; 
}

// int main(){
//     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//     #ifndef ONLINE_JUDGE
//         freopen("input1.txt", "r", stdin);
//         freopen("output1.txt", "w", stdout);
//         freopen("error1.txt", "w", stderr);
//     #endif // ONLINE_JUDGE

//         test{
//         	int N,M,K;
//         	cin>>N>>M>>K;
//         	vector<int> x(M);
//         	vector<int> y(M);
//         	vector<int> c(M);
//         	vector<int> arr(N);
//         	int H;
//         	cin>>H;
//         	fip(0,N){
//         		cin>>arr[i];
//         	}
//         	fip(0,M){
//         		cin>>x[i]>>y[i]>>c[i];
//         	}
//         	// for(auto y : x)
//         	// 	cout<<y<< " ";
//         	// cout<<nli;
//         	// cout<<" OK";
//         	cout<<solve(N,M,K,H,x,y,c,arr)<<nli;
//         }
        
//     cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
//     return 0;
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5204 KB Correct.
2 Correct 28 ms 5204 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5992 KB Correct.
2 Correct 26 ms 5980 KB Correct.
3 Correct 26 ms 6020 KB Correct.
4 Correct 33 ms 6152 KB Correct.
5 Correct 27 ms 6072 KB Correct.
6 Correct 25 ms 14196 KB Correct.
7 Correct 34 ms 14012 KB Correct.
8 Correct 19 ms 23124 KB Correct.
9 Correct 29 ms 5168 KB Correct.
10 Correct 27 ms 5180 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5920 KB Correct.
2 Correct 25 ms 6028 KB Correct.
3 Correct 28 ms 5972 KB Correct.
4 Correct 30 ms 5172 KB Correct.
5 Correct 29 ms 5076 KB Correct.
6 Correct 9 ms 12372 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 59048 KB Correct.
2 Correct 44 ms 5972 KB Correct.
3 Correct 27 ms 5976 KB Correct.
4 Correct 26 ms 6004 KB Correct.
5 Correct 30 ms 5164 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6128 KB Correct.
2 Correct 33 ms 6100 KB Correct.
3 Correct 58 ms 6140 KB Correct.
4 Correct 34 ms 14604 KB Correct.
5 Correct 27 ms 5128 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6168 KB Correct.
2 Correct 38 ms 6116 KB Correct.
3 Correct 93 ms 75228 KB Correct.
4 Correct 24 ms 11860 KB Correct.
5 Correct 28 ms 5076 KB Correct.
6 Correct 26 ms 6100 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6168 KB Correct.
2 Correct 7 ms 6740 KB Correct.
3 Correct 95 ms 93140 KB Correct.
4 Correct 76 ms 25212 KB Correct.
5 Correct 62 ms 41928 KB Correct.
6 Correct 39 ms 19644 KB Correct.
7 Correct 61 ms 27068 KB Correct.
8 Correct 52 ms 8432 KB Correct.
9 Correct 29 ms 6116 KB Correct.
10 Correct 28 ms 6172 KB Correct.
11 Correct 55 ms 6376 KB Correct.
12 Correct 31 ms 6168 KB Correct.
13 Correct 28 ms 6192 KB Correct.
14 Correct 80 ms 48228 KB Correct.
15 Correct 60 ms 16788 KB Correct.
16 Correct 28 ms 6212 KB Correct.
17 Correct 33 ms 6160 KB Correct.
18 Correct 29 ms 6164 KB Correct.
19 Correct 55 ms 6068 KB Correct.
20 Correct 7 ms 5168 KB Correct.
21 Correct 6 ms 5880 KB Correct.
22 Correct 7 ms 6356 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6092 KB Correct.
2 Correct 7 ms 6780 KB Correct.
3 Correct 118 ms 100168 KB Correct.
4 Correct 65 ms 11044 KB Correct.
5 Correct 68 ms 41864 KB Correct.
6 Correct 39 ms 19592 KB Correct.
7 Correct 75 ms 38676 KB Correct.
8 Correct 59 ms 6576 KB Correct.
9 Correct 29 ms 6176 KB Correct.
10 Correct 27 ms 6184 KB Correct.
11 Correct 287 ms 5264 KB Correct.
12 Correct 33 ms 6068 KB Correct.
13 Correct 41 ms 6136 KB Correct.
14 Correct 75 ms 42996 KB Correct.
15 Correct 73 ms 50892 KB Correct.
16 Correct 71 ms 21864 KB Correct.
17 Correct 53 ms 8512 KB Correct.
18 Correct 30 ms 6388 KB Correct.
19 Correct 30 ms 6204 KB Correct.
20 Correct 28 ms 6100 KB Correct.
21 Correct 63 ms 6076 KB Correct.
22 Correct 6 ms 5076 KB Correct.
23 Correct 5 ms 5864 KB Correct.
24 Correct 18 ms 6404 KB Correct.