답안 #41094 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41094	2018-02-12T16:27:50 Z	comtalyst	경주 (Race) (IOI11_race)	C++14	9 / 100	169 ms	26748 KB

race

/*
 *	Task: ioi11_race
 *	Lang: C/C++11
 *	Site: oj.uz
 *	Last Update: 12/2/2018
 */

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
using namespace std;

/* Note
----------------------------
Learned : 
Bugs found & solved :
Optimizations :
----------------------------
*/	

#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define long long long
#define MOD 1000000007
#define MAX (long)(1e16+5)
#define MIN (long)(-1e16-5)
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)

//int tmp[200005][2],tmp2[200005];

vector<pair<long,long>> adl[200005];
umap<long,long> s[200005];
long ls[200005],sid[200005],lv[200005],sc,n,m,mn=MAX;
void solve(long x,long f){
	long i,y,id,v,need,w;
	pair<long,long> mx={0,0};
	umap<long,long>::iterator it;
	lv[x] = lv[f]+1;
	for(i = 0; i < adl[x].size(); i++){
		y = adl[x][i].x;
		if(y == f) continue;
		solve(y,x);
		id = sid[y];
		mx = max(mx,{(long)s[id].size(),y});
	}
	if(mx.x){
		sid[x] = sid[mx.y];
	}
	else{
		sid[x] = ++sc;
		mx.y = 0;
	}
	for(i = 0; i < adl[x].size(); i++){
		y = adl[x][i].x;
		if(y == f || y == mx.y) continue;
		id = sid[y];
		it = s[id].begin();
		while(it != s[id].end()){
			v = (*it).x + ls[id];
			need = m-v-ls[sid[x]];
			if(s[sid[x]][need]){
				mn = min(mn,s[sid[x]][need]+(*it).y-lv[x]*2);
			}
			else{
				s[sid[x]].erase(need);
			}
			it++;
		}
		while(!s[id].empty()){
			if(s[sid[x]][v-ls[sid[x]]]){
				s[sid[x]][v-ls[sid[x]]] = min(s[sid[x]][v-ls[sid[x]]],(*s[id].begin()).y);
			}
			else{
				s[sid[x]][v-ls[sid[x]]] = (*s[id].begin()).y;
			}
			s[id].erase(s[id].begin());
		}
	}
	for(i = 0; i < adl[x].size(); i++){
		y = adl[x][i].x;
		w = adl[x][i].y;
		if(y == f){
			break;
		}
	}
	need = m-w-ls[sid[x]];
	if(s[sid[x]][need]){
		mn = min(mn,s[sid[x]][need]-lv[f]);
	}
	else{
		s[sid[x]].erase(need);
	}
	ls[sid[x]] += w;
	s[sid[x]][w - ls[sid[x]]] = lv[x];
}

long best_path(int _n,int _m,int _edl[][2],int _edw[]){			// f*ck you 0-based idx
	long i,j;

	n = _n;
	m = _m;
	for(i = 0; i < n-1; i++){
		adl[_edl[i][0]+1].emplace_back(_edl[i][1]+1,_edw[i]);
		adl[_edl[i][1]+1].emplace_back(_edl[i][0]+1,_edw[i]);
		if(_edw[i] == m){
			return 1;
		}
	}
	solve(1,0);
	if(mn != MAX){
		return mn;
	}
	else{
		return -1;
	}
}

/*main(){
	int t,i,j,k,_n,_m;
	
	FILEIN_;

	scanf("%d %d",&_n,&_m);
	for(i = 0; i < _n-1; i++){
		scanf("%d %d %d",&tmp[i][0],&tmp[i][1],&tmp2[i]);
	}
	printf(">> %lld\n",best_path(_n,_m,tmp,tmp2));

	return 0;	
}*/

Compilation message

race.cpp: In function 'void solve(long long int, long long int)':
race.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
race.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
race.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
race.cpp: In function 'long long int best_path(int, int, int (*)[2], int*)':
race.cpp:105:9: warning: unused variable 'j' [-Wunused-variable]
  long i,j;
         ^
race.cpp: In function 'void solve(long long int, long long int)':
race.cpp:93:10: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
  need = m-w-ls[sid[x]];
         ~^~
race.cpp:77:18: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(s[sid[x]][v-ls[sid[x]]]){
                 ~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	15992 KB	Output is correct
2	Correct	15 ms	16100 KB	Output is correct
3	Correct	15 ms	16280 KB	Output is correct
4	Correct	16 ms	16280 KB	Output is correct
5	Correct	14 ms	16280 KB	Output is correct
6	Correct	15 ms	16280 KB	Output is correct
7	Correct	19 ms	16316 KB	Output is correct
8	Correct	15 ms	16396 KB	Output is correct
9	Correct	14 ms	16396 KB	Output is correct
10	Correct	16 ms	16396 KB	Output is correct
11	Correct	15 ms	16396 KB	Output is correct
12	Correct	15 ms	16396 KB	Output is correct
13	Correct	15 ms	16396 KB	Output is correct
14	Correct	18 ms	16396 KB	Output is correct
15	Correct	16 ms	16396 KB	Output is correct
16	Correct	15 ms	16396 KB	Output is correct
17	Correct	16 ms	16396 KB	Output is correct
18	Correct	14 ms	16396 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	15992 KB	Output is correct
2	Correct	15 ms	16100 KB	Output is correct
3	Correct	15 ms	16280 KB	Output is correct
4	Correct	16 ms	16280 KB	Output is correct
5	Correct	14 ms	16280 KB	Output is correct
6	Correct	15 ms	16280 KB	Output is correct
7	Correct	19 ms	16316 KB	Output is correct
8	Correct	15 ms	16396 KB	Output is correct
9	Correct	14 ms	16396 KB	Output is correct
10	Correct	16 ms	16396 KB	Output is correct
11	Correct	15 ms	16396 KB	Output is correct
12	Correct	15 ms	16396 KB	Output is correct
13	Correct	15 ms	16396 KB	Output is correct
14	Correct	18 ms	16396 KB	Output is correct
15	Correct	16 ms	16396 KB	Output is correct
16	Correct	15 ms	16396 KB	Output is correct
17	Correct	16 ms	16396 KB	Output is correct
18	Correct	14 ms	16396 KB	Output is correct
19	Incorrect	15 ms	16396 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	15992 KB	Output is correct
2	Correct	15 ms	16100 KB	Output is correct
3	Correct	15 ms	16280 KB	Output is correct
4	Correct	16 ms	16280 KB	Output is correct
5	Correct	14 ms	16280 KB	Output is correct
6	Correct	15 ms	16280 KB	Output is correct
7	Correct	19 ms	16316 KB	Output is correct
8	Correct	15 ms	16396 KB	Output is correct
9	Correct	14 ms	16396 KB	Output is correct
10	Correct	16 ms	16396 KB	Output is correct
11	Correct	15 ms	16396 KB	Output is correct
12	Correct	15 ms	16396 KB	Output is correct
13	Correct	15 ms	16396 KB	Output is correct
14	Correct	18 ms	16396 KB	Output is correct
15	Correct	16 ms	16396 KB	Output is correct
16	Correct	15 ms	16396 KB	Output is correct
17	Correct	16 ms	16396 KB	Output is correct
18	Correct	14 ms	16396 KB	Output is correct
19	Incorrect	169 ms	26748 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	15992 KB	Output is correct
2	Correct	15 ms	16100 KB	Output is correct
3	Correct	15 ms	16280 KB	Output is correct
4	Correct	16 ms	16280 KB	Output is correct
5	Correct	14 ms	16280 KB	Output is correct
6	Correct	15 ms	16280 KB	Output is correct
7	Correct	19 ms	16316 KB	Output is correct
8	Correct	15 ms	16396 KB	Output is correct
9	Correct	14 ms	16396 KB	Output is correct
10	Correct	16 ms	16396 KB	Output is correct
11	Correct	15 ms	16396 KB	Output is correct
12	Correct	15 ms	16396 KB	Output is correct
13	Correct	15 ms	16396 KB	Output is correct
14	Correct	18 ms	16396 KB	Output is correct
15	Correct	16 ms	16396 KB	Output is correct
16	Correct	15 ms	16396 KB	Output is correct
17	Correct	16 ms	16396 KB	Output is correct
18	Correct	14 ms	16396 KB	Output is correct
19	Incorrect	15 ms	16396 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

답안 #41094

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 12.0

Subtask #3 0 / 22.0

Subtask #4 0 / 57.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 12.0

Subtask #3
0 / 22.0

Subtask #4
0 / 57.0