oj.uz

Submission #698446

# Submission time Handle Problem Language Result Execution time Memory
698446 2023-02-13T13:31:51 Z vjudge1 Fireworks (APIO16_fireworks) C++17
7 / 100
 94 ms 143252 KB 
    #include<bits/stdc++.h>
    #define maxn 1000000
    using namespace std;
    int n,m;
    vector<int> a[maxn];
    int p[maxn];
    int c[maxn];
    long long ans;
    multiset<long long> x[maxn];
    long long t[maxn];
    int pt[maxn];
    vector<long long> cur;
    void dfs(int u) {
    	if(a[u].size()==0) {
    		x[u].insert(c[u]);
    		x[u].insert(c[u]);
    		pt[u]=u;
    		t[u]=c[u];
    		return;
    	}
    	for(auto v:a[u]) {
    		dfs(v);
    	}
    	pt[u]=0;
    	for(auto v:a[u]) {
    		if(x[pt[v]].size()>x[pt[u]].size()) {
    			pt[u]=pt[v];
    		}
    	}
    	for(auto v:a[u]) {
    		if(pt[u]!=pt[v]) {
    			for(auto c:x[pt[v]]) {
    				x[pt[u]].insert(c);
    			}
    		}
    	}
    	int sz=a[u].size();
    	long long sum=0;
    	for(int i=0;i<sz-1;i++) {
    		sum+=(*x[pt[u]].rbegin());
    		x[pt[u]].erase(--x[pt[u]].end());
    	}
    	long long p1=(*x[pt[u]].rbegin());
    	x[pt[u]].erase(--x[pt[u]].end());
    	long long p2=(*x[pt[u]].rbegin());
    	x[pt[u]].erase(--x[pt[u]].end());
    	x[pt[u]].insert(p1+c[u]);
    	x[pt[u]].insert(p2+c[u]);
    	t[u]=p1+c[u];
    	ans+=(sum-(sz-1)*p1);
    	for(auto v:a[u]) {
    		ans+=(p1-t[v]);
    	}
    }
    int main() {
    	scanf("%d %d",&n,&m);
assert(n==1);
    	for(int i=2;i<=n+m;i++) {
    		scanf("%d %d",&p[i],&c[i]);
    		a[p[i]].push_back(i);
    	}
    	dfs(1);
    	printf("%lld\n",ans);
    	return 0;
    }

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:56:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |      scanf("%d %d",&n,&m);
      |      ~~~~~^~~~~~~~~~~~~~~
fireworks.cpp:59:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |       scanf("%d %d",&p[i],&c[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70740 KB Output is correct
2 Correct 32 ms 70772 KB Output is correct
3 Correct 33 ms 70672 KB Output is correct
4 Correct 41 ms 70724 KB Output is correct
5 Correct 32 ms 70772 KB Output is correct
6 Correct 33 ms 70708 KB Output is correct
7 Correct 32 ms 70704 KB Output is correct
8 Correct 32 ms 70792 KB Output is correct
9 Correct 32 ms 70716 KB Output is correct
10 Correct 37 ms 70824 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 143252 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70740 KB Output is correct
2 Correct 32 ms 70772 KB Output is correct
3 Correct 33 ms 70672 KB Output is correct
4 Correct 41 ms 70724 KB Output is correct
5 Correct 32 ms 70772 KB Output is correct
6 Correct 33 ms 70708 KB Output is correct
7 Correct 32 ms 70704 KB Output is correct
8 Correct 32 ms 70792 KB Output is correct
9 Correct 32 ms 70716 KB Output is correct
10 Correct 37 ms 70824 KB Output is correct
11 Runtime error 94 ms 143252 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70740 KB Output is correct
2 Correct 32 ms 70772 KB Output is correct
3 Correct 33 ms 70672 KB Output is correct
4 Correct 41 ms 70724 KB Output is correct
5 Correct 32 ms 70772 KB Output is correct
6 Correct 33 ms 70708 KB Output is correct
7 Correct 32 ms 70704 KB Output is correct
8 Correct 32 ms 70792 KB Output is correct
9 Correct 32 ms 70716 KB Output is correct
10 Correct 37 ms 70824 KB Output is correct
11 Runtime error 94 ms 143252 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -