oj.uz

답안 #292883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292883 2020-09-07T14:36:10 Z limabeans Power Plant (JOI20_power) C++17
0 / 100
 16 ms 23808 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



int n;
vector<int> g[maxn];
string s;

int best=0;

int dfs(int at, int p) {
    vector<int> ch;
    for (int to: g[at]) {
	if (to==p) continue;
	int rec=dfs(to,at);
	if (rec>0) {
	    ch.push_back(rec);
	}
    }
    int res=int(s[at]-'0'); // self
    
    if (!ch.empty()) {
	sort(ch.begin(), ch.end());

	// self + best child
	if (s[at]=='1') {
	    best=max(best,1+ch.back());
	}

	// join children thru us
	int sum = std::accumulate(ch.begin(), ch.end(), 0);
	res = max(res, sum - int(s[at]-'0'));
    }

    cout<<at+1<<": "<<res<<endl;
    cout<<"ch: ";
    for (int c: ch) cout<<c<<" ";
    cout<<endl;
				     
    
    best=max(best,res);
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	--u; --v;
	g[u].push_back(v);
	g[v].push_back(u);
    }
    
    cin>>s;
    dfs(0,-1);
    // for (int i=0; i<n; i++) {
    // 	dfs(i,-1);	
    // }
    cout<<best<<endl; 
    return 0;
}

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -