oj.uz

Submission #752135

# Submission time Handle Problem Language Result Execution time Memory
752135 2023-06-02T10:48:10 Z Muhammetali Cyberland (APIO23_cyberland) C++17
0 / 100
 2864 ms 2097152 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using ld=long double;
using str=string;

using pi=pair<int,int>;
using pl=pair<ll,ll>;
using pd=pair<ld,ld>;
#define mp make_pair
#define f first
#define s second

template<class T>using V=vector<T>;
using vi=V<int>;
using vb=V<bool>;
using vl=V<ll>;
using vd=V<ld>;
using vs=V<str>;
using vpi=V<pi>;
using vpl=V<pl>;
using vpd=V<pd>;

#define sz(x) int((x).size())
#define all(x) begin(x),end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>&a,const T&b){return int(lb(all(a),b)-a.begin());}
template<class T> int upb(V<T>&a,const T&b){return int(ub(all(a),b)-a.begin());}

#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define F0R(i,a) FOR(i,0,a-1)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define R0F(i,a) ROF(i,a-1,0)
#define rep(a) F0R(_,a)
#define each(a,x) for(auto& a:x)

const int MOD=1e9+7;//998244353;
const int MX=1e5+5;
const ll BIG=1e18;
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> using pqg=priority_queue<T,vector<T>,greater<T>>;

constexpr int pct(int x){return __builtin_popcount(x);}
constexpr int bits(int x){return x==0?0:31-__builtin_clz(x);}
constexpr int p2(int x){return 1<<x;}

ll cdiv(ll a, ll b){return a/b+((a^b)>0&&a%b);}
ll fdiv(ll a, ll b){return a/b-((a^b)<0&&a%b);}

template<class T>bool ckmin(T&a,const T&b){return b<a?a=b,1:0;}
template<class T>bool ckmax(T&a,const T&b){return a<b?a=b,1:0;}

double solve(int n,int m,int k,int h,vi x,vi y,vi c,vi arr){
	double ans[n];
	ans[0]=0;
	for(int i=1;i<n;i++)ans[i]=INT_MAX;
	vpi adj[n];
	for(int i=0;i<m;i++){
		adj[x[i]].pb({y[i],c[i]});
		adj[y[i]].pb({x[i],c[i]});
	}
	pqg<pair<double,int>>p;
	pi par[n];
	int cost[n];
	p.push({0,0});
	par[0].f=-1;
	while(!p.empty()){
		double sum=p.top().f;
		int k=p.top().s;
		p.pop();
		for(pi it:adj[k]){
			if(ans[it.f]>sum+it.s){
				ans[it.f]=sum+it.s;
				par[it.f].f=k;
				cost[it.f]=it.s;
				if(it.f!=0 && it.f!=h){
					if(arr[it.f]==0)ans[it.f]=0,par[it.f].s=0;
					else if(arr[it.f]==2)ans[it.f]/=2,par[it.f].s=2;
					else par[it.f].s=1;
				}
				if(it.f!=h)p.push({ans[it.f],it.f});
			}
		}
	}
	if(ans[h]==INT_MAX)return -1;
	vi v;
	while(h!=-1)v.pb(h),h=par[h].f;
	for(int i=1;i<sz(v)-1;i++){
		if(par[v[i]].s==0 || k==0){
			for(int j=i-1;j>0;j--){
				ans[v[i]]=(ans[v[i-1]]+cost[v[i]])/2;
			}
			ans[v[0]]=ans[v[i-1]]+cost[v[0]];
		}else if(par[v[i]].s==1)k--;
	}
	return ans[h];
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, vi, vi, vi, vi)':
cyberland.cpp:109:14: warning: array subscript -1 is below array bounds of 'double [(<anonymous> + 1)]' [-Warray-bounds]
  109 |  return ans[h];
      |         ~~~~~^

Subtask #1
0.0 / 5.0

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

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2864 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2503 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 2412 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 2385 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -