Submission #4017737
Source Code Expand
// ConsoleApplication9.cpp : アプリケーションのエントリ ポイントを定義します。
//
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 9999999999
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define p(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n)
#define ub(v,n) upper_bound(v.begin(), v.end(), n)
//#define int long long
using namespace std;
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };
ll gcd(ll x, ll y) {
ll m = max(x, y), n = min(x, y);
if (m%n == 0)return n;
else return gcd(m%n, n);
}
ll lcm(ll x, ll y) {
return x / gcd(x, y)*y;
}
ll myPow(ll x, ll n, ll m) {
if (n == 0)
return 1;
if (n % 2 == 0)
return myPow(x * x % m, n / 2, m);
else
return x * myPow(x, n - 1, m) % m;
}
ll pow2(ll a, ll n) {//aのn乗を計算します。
ll x = 1;
while (n > 0) {//全てのbitが捨てられるまで。
if (n & 1) {//1番右のbitが1のとき。
x = x * a;
}
a = a * a;
n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。
}
return x;
}
long long nCr(int n, int r) {
if (r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
long long ans = 1;
int i;
for (i = 1; i <= r; i++) {
ans *= n - r + i;
ans /= i;
}
return ans;
}
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
// 二項係数計算
long long COM(int n, int k) {
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
bool arr[100000100];
vector<ll>sosuu;
void Eratosthenes() {
ll N = 10000010;
int c = 0;
for (int i = 0; i < N; i++) {
arr[i] = 1;
}
for (ll i = 2; i < sqrt(N); i++) {
if (arr[i]) {
for (ll j = 0; i * (j + 2) < N; j++) {
arr[i *(j + 2)] = 0;
}
}
}
for (int i = 2; i < N; i++) {
if (arr[i]) {
sosuu.pb(i);
//cout << sosuu[c] << " ";
c++;
}
}
//cout << endl;
//cout << c << endl;
}
ll stoL(string s) {
ll n = s.length();
ll ans = 0;
for (int i = 0; i < n; i++) {
ans += pow2(10, n - i-1)*(ll)(s[i]-'0');
}
return ans;
}
vector<int> parent[1010],child[1010];
int cost[1010];
vector<int>leaf;
ll ans=0;
void dfs(int n){
if(n>0){
for(auto x:parent[n]){
cost[x]=min(cost[x],cost[n]);
dfs(x);
}
}
}
void dfs2(int n){
for(auto x:child[n]){
ans+=cost[x]-cost[n];
dfs2(x);
}
}
int main() {
REP(i,1010)cost[i]=1e9;
int N,M;cin>>N>>M;
FOR(i,1,N){
int P;cin>>P;
parent[i].pb(P);
child[P].pb(i);
}
REP(i,M){
int B,C;cin>>B>>C;
leaf.pb(B);
cost[B]=C;
}
cost[0]=0;
for(auto x:leaf){
dfs(x);
}
//REP(i,N){
//p(cost[i]);
//}
dfs2(0);
p(ans);
}
Submission Info
Submission Time |
|
Task |
B - PackDrop |
User |
Mojumbo |
Language |
C++14 (GCC 5.4.1) |
Score |
300 |
Code Size |
3804 Byte |
Status |
AC |
Exec Time |
3 ms |
Memory |
384 KB |
Judge Result
Set Name |
All |
Score / Max Score |
300 / 300 |
Status |
|
Set Name |
Test Cases |
All |
00_sample_1, 00_sample_2, 00_sample_3, 10_random_00_n_5, 10_random_01_n_10, 10_random_02_n_2, 10_random_03_n_7, 10_random_04_n_6, 20_random_00_n_64, 20_random_01_n_95, 20_random_02_n_20, 20_random_03_n_33, 20_random_04_n_91, 30_random_00_n_793, 30_random_01_n_611, 30_random_02_n_852, 40_random_00_n_1000, 40_random_01_n_1000, 50_edge_one_00_n_11, 50_edge_one_01_n_101, 50_edge_one_02_n_999, 98_almost_straight_00_n_1000, 98_almost_straight_01_n_1000, 98_almost_straight_02_n_1000, 99_straight_00_n_10, 99_straight_01_n_100, 99_straight_02_n_1000 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_1 |
AC |
1 ms |
256 KB |
00_sample_2 |
AC |
1 ms |
256 KB |
00_sample_3 |
AC |
1 ms |
256 KB |
10_random_00_n_5 |
AC |
1 ms |
256 KB |
10_random_01_n_10 |
AC |
1 ms |
256 KB |
10_random_02_n_2 |
AC |
1 ms |
256 KB |
10_random_03_n_7 |
AC |
1 ms |
256 KB |
10_random_04_n_6 |
AC |
1 ms |
256 KB |
20_random_00_n_64 |
AC |
1 ms |
256 KB |
20_random_01_n_95 |
AC |
1 ms |
256 KB |
20_random_02_n_20 |
AC |
1 ms |
256 KB |
20_random_03_n_33 |
AC |
1 ms |
256 KB |
20_random_04_n_91 |
AC |
1 ms |
256 KB |
30_random_00_n_793 |
AC |
2 ms |
384 KB |
30_random_01_n_611 |
AC |
2 ms |
384 KB |
30_random_02_n_852 |
AC |
2 ms |
384 KB |
40_random_00_n_1000 |
AC |
2 ms |
384 KB |
40_random_01_n_1000 |
AC |
2 ms |
384 KB |
50_edge_one_00_n_11 |
AC |
1 ms |
256 KB |
50_edge_one_01_n_101 |
AC |
1 ms |
256 KB |
50_edge_one_02_n_999 |
AC |
3 ms |
384 KB |
98_almost_straight_00_n_1000 |
AC |
2 ms |
384 KB |
98_almost_straight_01_n_1000 |
AC |
2 ms |
384 KB |
98_almost_straight_02_n_1000 |
AC |
2 ms |
384 KB |
99_straight_00_n_10 |
AC |
1 ms |
256 KB |
99_straight_01_n_100 |
AC |
1 ms |
256 KB |
99_straight_02_n_1000 |
AC |
2 ms |
384 KB |