oj.uz

답안 #198565

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

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

const int sim=100010;

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];
long long mjaw,mind;

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());
	reverse(sem[x].begin(),sem[x].end());
	if(sem[x].size()==0) return dp[x]=0;
	else return dp[x]=sem[x][0].fi;
}

long long cari2(int x,long long baw){
	if(sem[x].size()==0) return baw;
	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]));
//	cout<<"dp "<<x<<' '<<dp[x]<<endl;
	for(int i=0; i<sem[x].size(); i++){
		long long seu=baw;
		if(i==0){
			seu=max(seu,sem[x][1].fi);
		}else {
			seu=max(seu,sem[x][0].fi);
		}
		maxi=min(maxi,cari2(sem[x][i].se.fi,seu+sem[x][i].se.se));
	}
//	cout<<x<<' '<<maxi<<endl;
//	return maxi;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    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);
		udah[x]=1;	
	}
	long long has=0;
	vector<long long> jaw;
	//cout<<v.size()<<endl;
	for(int i=0; i<v.size(); i++){
	//	cout<<v[i]<<endl;
		cari(v[i],-1);
		long long baw=0;
//		if(sem[v[i]].size()>1){
//			baw=sem[v[i]][1].fi;
//		}
	//	mjaw=1e18;
		if(sem[v[i]].size()>1){
			has=max(has,sem[v[i]][0].fi+sem[v[i]][1].fi);
		}else if(sem[v[i]].size()==1){
			has=max(has,dp[v[i]]);
		}
		long long wk=cari2(v[i],baw);
	//	cout<<wk<<endl<<endl;
		jaw.push_back(wk);
	}
	sort(jaw.begin(),jaw.end());
	reverse(jaw.begin(),jaw.end());
//	if(jaw.size()<=1){
//		for(int i=1; i<=1e9; i++){
//		}
//	}
	if(jaw.size()>=2){
		has=max(has,jaw[1]+jaw[0]+l);
//		for(int i=1; i<=1e9; i++){
//		}
	}
	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:24: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:43: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:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
dreaming.cpp: In function 'long long int cari2(int, long long int)':
dreaming.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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