oj.uz

답안 #198442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198442 2020-01-26T04:20:46 Z Sakamotoo 꿈 (IOI13_dreaming) C++14
0 / 100
 1000 ms 27504 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define fi first
#define se second

const int sim=100000;

int p[sim];
bool udah[sim];
vector<pair<int,int> > adj[sim];
long long dp[sim];
vector<pair<long long,pair<int,int> > >sem[sim];

int par(int x){
	if(p[x]==x) return x;
	else return p[x]=par(p[x]);
}

long long cari(int x, int seb){
	for(int i=0; i<adj[x].size(); i++){
		int ind=adj[x][i].fi;
		if(ind!=seb){
			sem[x].push_back(mp(cari(ind,x)+adj[x][i].se,mp(ind,adj[x][i].se)));
		}
	}
	sort(sem[x].begin(),sem[x].end());
	if(sem[x].size()==0) return 0;
	else return sem[x][0].fi;
}

long long cari2(int x,long long baw){
	if(sem[x].size()==0) return 1e18;
	if(sem[x].size()>1)baw=max(baw,sem[x][1].fi);
	long long pen=sem[x][0].fi;
	long long maxi=1e18;
	maxi=min(maxi,max(baw,dp[x]));
	for(int i=0; i<sem[x].size(); i++){
		if(sem[x][i].fi==pen){
			maxi=min(maxi,cari2(sem[x][i].se.fi,baw+sem[x][i].se.se));
		}
	}
	return maxi;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	memset(dp,-1,sizeof dp);
    for(int i=0; i<n; i++){
    	p[i]=i;
	}
	for(int i=0; i<m; i++){
		adj[a[i]].push_back(mp(b[i],t[i]));
		adj[b[i]].push_back(mp(a[i],t[i]));
		
		int x=par(a[i]),y=par(b[i]);
		p[x]=y;
	}
	vector<int> v;
	
	for(int i=0; i<n; i++){
		int x=par(i);
		if(!udah[x]) v.push_back(x);
	}
	
	vector<long long> jaw;
	for(int i=0; i<v.size(); i++){
		cari(v[i],-1);
		long long baw=0;
		if(sem[v[i]].size()>1){
			baw=sem[v[i]][1].fi;
		}
		jaw.push_back(cari2(v[i],baw));
	}
	sort(jaw.begin(),jaw.end());
	long long has=jaw[0];
	if(jaw.size()>=2){
		has=max(has,jaw[1]+jaw[0]+l);
	}
	if(jaw.size()>=3){
		has=max(has,jaw[1]+jaw[2]+l+l);
	}
	return has;
}

Compilation message

dreaming.cpp: In function 'long long int cari(int, int)':
dreaming.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[x].size(); i++){
               ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int cari2(int, long long int)':
dreaming.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<sem[x].size(); i++){
               ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:68:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 11760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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