Submission #496710

#	Time	Username	Problem	Language	Result	Execution time	Memory
496710		jamezzz	Power Plant (JOI20_power)	C++17	100 / 100	164 ms	25088 KiB

power

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
    int x=0;
    char ch=getchar_unlocked();
    while(ch<'0'||ch>'9')ch=getchar_unlocked();
    while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar_unlocked();
	}
    return x;
}

#define maxn 200005

int n,a,b,ans;
vi AL[maxn];
char s[maxn];

int dfs(int u,int p){
	int v0=0,v1=0,sm=0,mx=0;
	for(int v:AL[u]){
		if(v==p)continue;
		int tmp=dfs(v,u);
		sm+=max(tmp,0);
		mx=max(mx,tmp);
	}
	int t=(s[u-1]-'0');
	v0=max(sm-t,mx+t);//first one
	v1=max(sm-t,t);//>1 on top
	ans=max(ans,max(v0,v1));
	return v1;
}

int main(){
	sf("%d",&n);
	for(int i=1;i<n;++i){
		sf("%d%d",&a,&b);
		AL[a].pb(b);
		AL[b].pb(a);
	}
	sf(" %s",&s);
	dfs(1,1);
	pf("%d\n",ans);
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:85:8: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[200005]' [-Wformat=]
   85 |  sf(" %s",&s);
      |       ~^  ~~
      |        |  |
      |        |  char (*)[200005]
      |        char*
power.cpp:79:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  sf("%d",&n);
      |    ^
power.cpp:81:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   sf("%d%d",&a,&b);
      |     ^
power.cpp:85:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  sf(" %s",&s);
      |    ^

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53