제출 #698445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
698445		vjudge1	Fireworks (APIO16_fireworks)	C++17	100 / 100	391 ms	150896 KiB

fireworks

    #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);
    	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;
    }

컴파일 시 표준 에러 (stderr) 메시지

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:58:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |       scanf("%d %d",&p[i],&c[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45