oj.uz

답안 #72330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72330 2018-08-26T07:11:50 Z nvmdava 꿈 (IOI13_dreaming) C++17
0 / 100
 182 ms 31708 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

struct Path{
	int to, cost;
	Path(int _to, int _cost){
		to = _to;
		cost = _cost;
	}
};

struct Node{
	int p[20], d;
};
map<int, int> c[100001];
vector<Path> path[100001];
bool in[100001];
Node a[100001];
int mxdist, mxid;
int solo = 0;
void build(int v, int p){
	in[v] = 1;
	for(auto x : path[v]){
		if(x.to == p) continue;
		a[x.to].d = a[v].d + 1;
		memset(a[x.to].p, -1, sizeof(a[x.to].p));
		a[x.to].p[0] = v;
		for(int i = 1; i < 20; i++){
			int t = a[x.to].p[i - 1];
			if(t == -1) break;
			a[x.to].p[i] = a[t].p[i - 1];
		}
		build(x.to, v);
	}
}

int goUp(int v, int u){
	for(int i = 0; i < 20; i++){
		if(u & (1 << i)) v = a[v].p[i];
	}
	return v;
}

int lca(int v, int u){
	int l = 0;
	int r = min(a[v].d, a[u].d) + 1;
	int m;
	while(l + 1 != r){
		m = (l + r) >> 1;
		if(goUp(v, a[v].d - m) == goUp(u, a[u].d - m)) l = m;
		else r = m;
	}
	return goUp(v, a[v].d - l);
}

void dfs(int v, int p, int d){
	if(path[v].size() == 1 && p != -1){
		if(d > mxdist){
			mxdist = d;
			mxid = v;
		}
	}
	for(auto x : path[v]){
		if(x.to == p) continue;
		dfs(x.to, v, d + x.cost);
	}
}

int comp = 0;

int go(int v){
	if(in[v]) return 0;
	comp++;
	if(path[v].size() == 0) return 0;
	memset(a[v].p, -1, sizeof(a[v].p));
	a[v].d = 0;
	build(v, -1);
	
	mxdist = 0;
	mxid = v;
	dfs(v, -1, 0);
	mxdist = 0;
	v = mxid;
	dfs(v, -1, 0);
	int u = mxid;
	int o = lca(v, u);
	solo = max(solo, mxdist);
	int s = (mxdist + 1) >> 1;
	int q = 0;
	while(v != o){
		q += c[v][a[v].p[0]];
		if(q >= s){
			return min(q, mxdist - q + c[v][a[v].p[0]]);
		}
		v = a[v].p[0];
	}
	q = 0;
	while(u != o){
		q += c[u][a[u].p[0]];
		if(q >= s){
			return min(q, mxdist - q + c[u][a[u].p[0]]);
		}
		u = a[u].p[0];
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    
    for(int i = 0; i < M; i++){
    	path[A[i]].push_back(Path(B[i], T[i]));
    	path[B[i]].push_back(Path(A[i], T[i]));
    	c[A[i]][B[i]] = T[i];
    	c[B[i]][A[i]] = T[i];
	}
	int mx = 0;
	int mx2 = 0;
	int mx3 = 0;
	int s;
	for(int i = 0; i < N; i++){
		s = go(i);
		if(s > mx){
			mx3 = mx2;
			mx2 = mx;
			mx = s;
		} else if(s > mx2){
			mx3 = mx2;
			mx2 = s;
		} else {
			mx3 = max(mx3, s);
		}
	}
	if(comp == 1) return solo;
	return max(L + mx + mx2, max(solo, mx3 + mx2 + L * 2));
}

Compilation message

dreaming.cpp: In function 'int go(int)':
dreaming.cpp:106:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 31708 KB Output is correct
2 Correct 182 ms 31608 KB Output is correct
3 Correct 91 ms 23416 KB Output is correct
4 Correct 21 ms 10880 KB Output is correct
5 Correct 18 ms 9856 KB Output is correct
6 Correct 34 ms 12792 KB Output is correct
7 Incorrect 8 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 31708 KB Output is correct
2 Correct 182 ms 31608 KB Output is correct
3 Correct 91 ms 23416 KB Output is correct
4 Correct 21 ms 10880 KB Output is correct
5 Correct 18 ms 9856 KB Output is correct
6 Correct 34 ms 12792 KB Output is correct
7 Incorrect 8 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 31708 KB Output is correct
2 Correct 182 ms 31608 KB Output is correct
3 Correct 91 ms 23416 KB Output is correct
4 Correct 21 ms 10880 KB Output is correct
5 Correct 18 ms 9856 KB Output is correct
6 Correct 34 ms 12792 KB Output is correct
7 Incorrect 8 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 20344 KB Output is correct
2 Correct 69 ms 20464 KB Output is correct
3 Correct 75 ms 20476 KB Output is correct
4 Correct 74 ms 20472 KB Output is correct
5 Correct 69 ms 20344 KB Output is correct
6 Correct 74 ms 21240 KB Output is correct
7 Correct 67 ms 20984 KB Output is correct
8 Correct 62 ms 20216 KB Output is correct
9 Correct 67 ms 20216 KB Output is correct
10 Correct 71 ms 20856 KB Output is correct
11 Correct 7 ms 7424 KB Output is correct
12 Correct 10 ms 9600 KB Output is correct
13 Correct 12 ms 11008 KB Output is correct
14 Correct 14 ms 9444 KB Output is correct
15 Correct 10 ms 9856 KB Output is correct
16 Correct 9 ms 9088 KB Output is correct
17 Correct 8 ms 7808 KB Output is correct
18 Correct 12 ms 11776 KB Output is correct
19 Correct 9 ms 9088 KB Output is correct
20 Correct 8 ms 7424 KB Output is correct
21 Incorrect 8 ms 7424 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 31708 KB Output is correct
2 Correct 182 ms 31608 KB Output is correct
3 Correct 91 ms 23416 KB Output is correct
4 Correct 21 ms 10880 KB Output is correct
5 Correct 18 ms 9856 KB Output is correct
6 Correct 34 ms 12792 KB Output is correct
7 Incorrect 8 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 31708 KB Output is correct
2 Correct 182 ms 31608 KB Output is correct
3 Correct 91 ms 23416 KB Output is correct
4 Correct 21 ms 10880 KB Output is correct
5 Correct 18 ms 9856 KB Output is correct
6 Correct 34 ms 12792 KB Output is correct
7 Incorrect 8 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -