oj.uz

Submission #30776

# Submission time Handle Problem Language Result Execution time Memory
30776 2017-07-26T12:47:36 Z inqr Fireworks (APIO16_fireworks) C++14
0 / 100
 3 ms 16084 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define ll long long
#define pii pair < int , int >
#define DB printf("debug\n");
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define all(x) x.begin() , x.end()
#define MAXN 300005
using namespace std;
int n,m,cost=0;
vector < pii > ed[MAXN];
vector < pii > weights[MAXN];
int dfs(int vn){
	printf("1:dfs vn=%d\n",vn);
	if(ed[vn].size()==0)return 0;
	printf("2:dfs vn=%d\n",vn);
	for(int i=0;i<ed[vn].size();i++){
		weights[vn].pb(mp(ed[vn][i].nd+dfs(ed[vn][i].st),ed[vn][i].st));
	}
	sort(all(weights[vn]));
	int ws=weights[vn].size();
	return weights[vn][ws/2].st;
}

int dfsold(int vn){
	if(ed[vn].size()==0)return 0;
	//printf("2:dfs vn=%d\n",vn);
	for(int i=0;i<ed[vn].size();i++){
		weights[vn].pb(mp(ed[vn][i].nd+dfsold(ed[vn][i].st),ed[vn][i].st));
	}
	sort(all(weights[vn]));
	int ws=weights[vn].size();
	for(int i=0;i<ws;i++){
		//printf("1:vn=%d iwei=%d medwei=%d cost=%d\n",vn,weights[vn][i].st,weights[vn][ws/2].st,cost);
		cost+=abs(weights[vn][i].st-weights[vn][(ws-1)/2].st);
		//printf("  3:vn=%d iwei=%d medwei=%d cost=%d\n",vn,weights[vn][i].st,weights[vn][(ws-1)/2].st,cost);
	}
	return weights[vn][((ws-1))/2].st;
}
int main(){
	//cin.tie(0);ios_base::sync_with_stdio(0);
	freopen("fireworks.in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m;
	for(int i=2;i<=n+m;i++){
		int c1,c2;cin>>c1>>c2;
		ed[c1].pb(mp(i,c2));
	}
	dfsold(2);
	cout<<cost<<endl;
	return 0;
}

Compilation message

fireworks.cpp: In function 'int dfs(int)':
fireworks.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed[vn].size();i++){
               ^
fireworks.cpp: In function 'int dfsold(int)':
fireworks.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed[vn].size();i++){
               ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:47:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("fireworks.in","r",stdin);
                                   ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16084 KB Output is correct
2 Incorrect 3 ms 16084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16084 KB Output is correct
2 Incorrect 3 ms 16084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16084 KB Output is correct
2 Incorrect 3 ms 16084 KB Output isn't correct
3 Halted 0 ms 0 KB -