oj.uz

답안 #244910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244910 2020-07-05T09:12:46 Z Red_Inside Fireworks (APIO16_fireworks) C++17
0 / 100
 49 ms 43392 KB 
#include <bits/stdc++.h>
#include <random>

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
//tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define	IOS ios_base::sync_with_stdio(0);
#define en "\n"
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define sortv(vv) sort(vv.begin(), vv.end())
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
const ll maxn=3e5+100,inf=1e9,LOG=23,mod=1e9+7;
ll block = 500, timer = 0;
const ld EPS = 1e-7;

#define bt(i) (1 << (i))
//#define int ll
#define y1 yy
//#define double long double
#define pii pair <int, int>

int n, m, a[maxn], b[maxn], c[maxn];
multiset <int> st[maxn];
vector <int> edge[maxn];

void dfs(int v)
{
	if(edge[v].size() == 0)
	{
		st[v].insert(c[v]);
		st[v].insert(c[v]);
		a[v] = 1;
		b[v] = -c[v];
		/*cout << "V " << v << "  - ";
		for(auto i : st[v])
		{
			cout << i << " ";
		}
		cout << "  " << a[v] << " " << b[v] << endl;*/
		return;
	}
	for(auto to : edge[v])
	{
		dfs(to);
		if(st[to].size() > st[v].size()) swap(st[v], st[to]);
		while(st[to].size())
		{
			st[v].insert(*st[to].begin());
			st[to].erase(st[to].begin());
		}
		a[v] += a[to];
		b[v] += b[to];
	}
	while(a[v] > 1)
	{
		auto it = st[v].end();
		it--;
		b[v] += *it;
		st[v].erase(it);
		a[v]--;
	}
	auto it = st[v].end();
	it--;
	int c1 = *it;
	it--;
	int c2 = *it;
	st[v].erase(c1);
	st[v].insert(c1 + c[v]);
	st[v].erase(c2);
	st[v].insert(c2 + c[v]);
	b[v] -= c[v];
	/*cout << "V " << v << "  - ";
	for(auto i : st[v])
	{
		cout << i << " ";
	}
	cout << "  " << a[v] << " " << b[v] << endl;*/
}

main()
{
	IOS
	cin >> n >> m;
	n += m;
	forn(2, i, n)
	{
		int p;
		cin >> p >> c[i];
		edge[p].pb(i);
	}
	dfs(1);
	while(a[1] > 0)
	{
		auto it = st[1].end();
		it--;
		a[1]--;
		b[1] += *it;
		st[1].erase(it);
	}
	cout << b[1] + a[1] * (*st[1].rbegin());
}

Compilation message

fireworks.cpp:9:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
fireworks.cpp:99:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 49 ms 43388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 21504 KB Output is correct
2 Correct 18 ms 21504 KB Output is correct
3 Correct 17 ms 21504 KB Output is correct
4 Runtime error 41 ms 43392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 49 ms 43388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 49 ms 43388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -