oj.uz

Submission #29370

# Submission time Handle Problem Language Result Execution time Memory
29370 2017-07-19T07:45:24 Z dereotu Race (IOI11_race) C++14
9 / 100
 3000 ms 10996 KB 
#include "race.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define forr(i,A,B) for(int i=A;i<B;++i)
#define space ' '
#define endl '\n'
#define LL long long
using namespace std;

vector <pair<int,int> > adj[200005];

int ans=1e9;
int used[200005],sub[200005];
int k;

int calc_sub(int x,int y){
	sub[x]=1;
	forr(i,0,adj[x].size()){
		if(adj[x][i].nd!=y){
			sub[x]+=calc_sub(adj[x][i].nd,x);
		}
	}
	return sub[x];
}

int find_centroid(int x,int y,int treesize){
	forr(i,0,adj[x].size()){
		if(!used[adj[x][i].nd] and adj[x][i].nd!=y and sub[adj[x][i].nd]>treesize/2){
			return find_centroid(adj[x][i].nd,x,k);
		}
	}
	return x;
}

void dfs(int x,int y,int length,int path,map<int,int> &small_map){
	if(length>k) return;
	if(small_map.find(length)==small_map.end()){
		small_map[length]=path;
	}
	else small_map[length]=min(small_map[length],path);
	forr(i,0,adj[x].size()){
		if(adj[x][i].nd!=y and !used[adj[x][i].nd]){
			dfs(adj[x][i].nd,x,length+adj[x][i].st,path+1,small_map);
		}
	}
}

void merge(map<int,int> &a,map<int,int> &b){//iki mapi birleştirip cevabı updateler
	for(auto it=b.begin();it!=b.end();it++){
		if(a.find(k-it->st)!=a.end()){
			ans=min(ans,a[k-it->st]+it->nd);
		}
	}
	for(auto it=b.begin();it!=b.end();it++){
		if(a.find(it->st)==a.end()){
			a[it->st]=it->nd;
		}
		else{
			a[it->st]=min(a[it->st],it->nd);
		}
	}
}

void calc(int x){//bir subtree için cevabı updateler
	map<int,int> main_map;
	main_map[0]=0;
	forr(i,0,adj[x].size()){
		if(!used[adj[x][i].nd]){
			map<int,int> sub_map;
			dfs(x,-1,0,0,sub_map);
			merge(main_map,sub_map);
		}
	}
}

void solve(int x){
	calc_sub(x,-1);
	int centroid=find_centroid(x,-1,sub[x]);
	used[x]=1;
	calc(x);
	forr(i,0,adj[x].size()){
		if(!used[adj[x][i].nd]){
			solve(adj[x][i].nd);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	for(int i=0;i<N;i++){
		adj[H[i][0]].pb(mp(L[i],H[i][1]));
		adj[H[i][1]].pb(mp(L[i],H[i][0]));
	}
	k=K;
	solve(0);
	if(ans==1e9) return -1;
	else return ans;
}

Compilation message

race.cpp: In function 'int calc_sub(int, int)':
race.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
race.cpp:22:7:
  forr(i,0,adj[x].size()){
       ~~~~~~~~~~~~~~~~~           
race.cpp:22:2: note: in expansion of macro 'forr'
  forr(i,0,adj[x].size()){
  ^~~~
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
race.cpp:31:7:
  forr(i,0,adj[x].size()){
       ~~~~~~~~~~~~~~~~~           
race.cpp:31:2: note: in expansion of macro 'forr'
  forr(i,0,adj[x].size()){
  ^~~~
race.cpp: In function 'void dfs(int, int, int, int, std::map<int, int>&)':
race.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
race.cpp:45:7:
  forr(i,0,adj[x].size()){
       ~~~~~~~~~~~~~~~~~           
race.cpp:45:2: note: in expansion of macro 'forr'
  forr(i,0,adj[x].size()){
  ^~~~
race.cpp: In function 'void calc(int)':
race.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
race.cpp:71:7:
  forr(i,0,adj[x].size()){
       ~~~~~~~~~~~~~~~~~           
race.cpp:71:2: note: in expansion of macro 'forr'
  forr(i,0,adj[x].size()){
  ^~~~
race.cpp: In function 'void solve(int)':
race.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
race.cpp:85:7:
  forr(i,0,adj[x].size()){
       ~~~~~~~~~~~~~~~~~           
race.cpp:85:2: note: in expansion of macro 'forr'
  forr(i,0,adj[x].size()){
  ^~~~
race.cpp:82:6: warning: unused variable 'centroid' [-Wunused-variable]
  int centroid=find_centroid(x,-1,sub[x]);
      ^~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 5124 KB Output is correct
3 Correct 6 ms 5156 KB Output is correct
4 Correct 6 ms 5156 KB Output is correct
5 Correct 8 ms 5236 KB Output is correct
6 Correct 7 ms 5236 KB Output is correct
7 Correct 6 ms 5236 KB Output is correct
8 Correct 6 ms 5296 KB Output is correct
9 Correct 7 ms 5296 KB Output is correct
10 Correct 6 ms 5296 KB Output is correct
11 Correct 6 ms 5376 KB Output is correct
12 Correct 6 ms 5376 KB Output is correct
13 Correct 6 ms 5376 KB Output is correct
14 Correct 7 ms 5376 KB Output is correct
15 Correct 6 ms 5376 KB Output is correct
16 Correct 7 ms 5376 KB Output is correct
17 Correct 6 ms 5376 KB Output is correct
18 Correct 7 ms 5376 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 5124 KB Output is correct
3 Correct 6 ms 5156 KB Output is correct
4 Correct 6 ms 5156 KB Output is correct
5 Correct 8 ms 5236 KB Output is correct
6 Correct 7 ms 5236 KB Output is correct
7 Correct 6 ms 5236 KB Output is correct
8 Correct 6 ms 5296 KB Output is correct
9 Correct 7 ms 5296 KB Output is correct
10 Correct 6 ms 5296 KB Output is correct
11 Correct 6 ms 5376 KB Output is correct
12 Correct 6 ms 5376 KB Output is correct
13 Correct 6 ms 5376 KB Output is correct
14 Correct 7 ms 5376 KB Output is correct
15 Correct 6 ms 5376 KB Output is correct
16 Correct 7 ms 5376 KB Output is correct
17 Correct 6 ms 5376 KB Output is correct
18 Correct 7 ms 5376 KB Output is correct
19 Correct 5 ms 5376 KB Output is correct
20 Correct 6 ms 5376 KB Output is correct
21 Incorrect 56 ms 5376 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 5124 KB Output is correct
3 Correct 6 ms 5156 KB Output is correct
4 Correct 6 ms 5156 KB Output is correct
5 Correct 8 ms 5236 KB Output is correct
6 Correct 7 ms 5236 KB Output is correct
7 Correct 6 ms 5236 KB Output is correct
8 Correct 6 ms 5296 KB Output is correct
9 Correct 7 ms 5296 KB Output is correct
10 Correct 6 ms 5296 KB Output is correct
11 Correct 6 ms 5376 KB Output is correct
12 Correct 6 ms 5376 KB Output is correct
13 Correct 6 ms 5376 KB Output is correct
14 Correct 7 ms 5376 KB Output is correct
15 Correct 6 ms 5376 KB Output is correct
16 Correct 7 ms 5376 KB Output is correct
17 Correct 6 ms 5376 KB Output is correct
18 Correct 7 ms 5376 KB Output is correct
19 Execution timed out 3045 ms 10996 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 5124 KB Output is correct
3 Correct 6 ms 5156 KB Output is correct
4 Correct 6 ms 5156 KB Output is correct
5 Correct 8 ms 5236 KB Output is correct
6 Correct 7 ms 5236 KB Output is correct
7 Correct 6 ms 5236 KB Output is correct
8 Correct 6 ms 5296 KB Output is correct
9 Correct 7 ms 5296 KB Output is correct
10 Correct 6 ms 5296 KB Output is correct
11 Correct 6 ms 5376 KB Output is correct
12 Correct 6 ms 5376 KB Output is correct
13 Correct 6 ms 5376 KB Output is correct
14 Correct 7 ms 5376 KB Output is correct
15 Correct 6 ms 5376 KB Output is correct
16 Correct 7 ms 5376 KB Output is correct
17 Correct 6 ms 5376 KB Output is correct
18 Correct 7 ms 5376 KB Output is correct
19 Correct 5 ms 5376 KB Output is correct
20 Correct 6 ms 5376 KB Output is correct
21 Incorrect 56 ms 5376 KB Output isn't correct
22 Halted 0 ms 0 KB -