oj.uz

답안 #751034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751034 2023-05-30T20:25:48 Z Rejep 사이버랜드 (APIO23_cyberland) C++17
0 / 100
 3000 ms 2097152 KB 
#include "cyberland.h"



#include<bits/stdc++.h>

#define db double

#define pb push_back

#define ft first

#define sd second

using namespace std;

const db INF=1e18+1;

vector<vector<pair<int,db>>>g(1e5);

vector<bool>vis(1e5,0), ar(1e5,0);

vector<int>arr;

int n, m, k, h;



void dfs(int x){

	vis[x]=1;

	if (x==h)return;

	if (arr[x]==0)ar[x]=1;

	for (auto u:g[x]){

		if (!vis[u.ft]){

			dfs(u.ft);

		}

	}

}



db pw(db x, int y){

	if (!y)return 1;

	if (y % 2)return pw(x, y-1)*x;

	db tmp=pw(x, y/2);

	return tmp*tmp;

}



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;k=K;h=H;arr=ARR;

	for (int i=0; i<n; i++){

		g[i].clear();

		vis[i]=0;

		ar[i]=0;

	}

	for (int i=0; i<m; i++){

		g[x[i]].pb({y[i],c[i]});

		g[y[i]].pb({x[i],c[i]});

	}

	arr[0]=0;

	

	dfs(0);

	

	vector<int> ls (n, -1);

	ls[h] = 0;

	vector<bool> u1 (n, 0);

	for (int i=0; i<n; ++i) {

		int v = -1;

		for (int j=1; j<n; ++j)

			if (!u1[j] && (v == -1 || ls[j] > ls[v]))

				v = j;

		if (v==-1||ls[v]==-1)

			break;

		u1[v] = 1;

 

		for (int j=0; j<(int)g[v].size(); ++j) {

			int to = g[v][j].ft;

			if (u1[to])continue;

			if (arr[to]==2){

				ls[to]=max(ls[v]+1,ls[to]);

			}else ls[to]=max(ls[v],ls[to]);

			

		}

	}

	

	vector<db> d (n, INF);

	d[h] = 0;

	vector<bool> u (n, 0);

	for (int i=0; i<n; ++i) {

		int v = -1;

		for (int j=0; j<n; ++j)

			if (!u[j] && (v == -1 || d[j] < d[v]))

				v = j;

		if (d[v] == INF)

			break;

		u[v] = 1;

 

		for (int j=0; j<(int)g[v].size(); ++j) {

			int to = g[v][j].ft;

			db len = g[v][j].sd;

			db k2=pw(2.0,min(ls[v],k));

			if (d[v] + (len / k2) < d[to]) {

				d[to] = d[v] + len/k2;

			}

		}

	}

	

	db ans = INF;

	for (int i=0; i<n; i++){

		if (ar[i])ans=min(ans,d[i]);

	}

	

	if (ans==INF)return -1;

	else return ans;

}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 950 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 879 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 900 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3072 ms 8020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 910 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 942 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 919 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 894 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -