oj.uz

Submission #705808

# Submission time Handle Problem Language Result Execution time Memory
705808 2023-03-05T10:34:55 Z hoangnghiep Beads and wires (APIO14_beads) C++14
100 / 100
 310 ms 47300 KB 
#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define repeat(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define p push
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
//#define DEBUG
//#define multipletest
using namespace std;
const int LIM=2e5;
const int mod=1e9+7;
const int maxn=20;
const int inf=1e9;
int n,m,x,y,k,t,e,q;
int dx[8]={-1,0,1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
char c;
string s;
int a[LIM+5],factorial[(1<<maxn)+5],inv_fact[(1<<maxn)+5];
bool notprime[LIM+5];
map<int,int> mp;
char grid[100+5][100+5];
vector<pii> adj[LIM+5];
int power(int a,int b){
   if(b==0) return 1;
    int t=power(a,b/2);
    t = t * t %mod;
    if(b%2==1) t = t * a %mod;
    return t;
}
bool check(int x,int y){
    if(x<=0 || x>n || y<=0 || y>m || grid[x][y]=='T'){
   return false;
     }
    return true;
}
class DSU{
	int *parent;
	int *rank;
	int *tot;
	public:
	DSU(int n){
		rank=new int[n+5];
		parent=new int[n+5];
		tot=new int [n+5];
		for(int i=0;i<n+5;i++){
			parent[i]=i;
			rank[i]=0;
			tot[i]=1;
		}
	}
	int find(int i){
		if(parent[i]==i){
			return i;
		}
		return parent[i]=find(parent[i]);
	}
	void unite(int u,int v){
		int i=find(u);
		int j=find(v);
		if(i!=j){
			if(rank[i]>rank[j]){
				parent[j]=i;
				tot[i]+=tot[j];
			}
			else if(rank[i]<rank[j]){
				parent[i]=j;
				tot[j]+=tot[i];
			}
			else{
				parent[j]=i;
				rank[i]++;
				tot[i]+=tot[j];
			}
		}
	}
	int total(int u){
	   return tot[u];
	}
};
void precal(int n){
	factorial[0]=1;
	inv_fact[0]=1;
    for (int i = 1; i <n; ++i)
	{
		factorial[i] = factorial[i - 1] * i % mod;
		inv_fact[i] = inv_fact[i - 1] * power(i, mod - 2) % mod;
	}
}
int choose(int n,int k){
	if(k<0 || k>n) return 0;
	return factorial[n] * inv_fact[n-k] % mod * inv_fact[k] %mod;
}
void Sieve(){
	notprime[0]=notprime[1]=true;
    for(int i=2;i<LIM+5;++i){
    	if(notprime[i]==false){
    	for(int j=i*i;j<LIM+5;j+=i){
    		notprime[j]=true;
		}
    }
	}
}
int f[LIM+5][2];
multiset<int> tp[LIM+5];
int ans;
void dfs(int u,int parent){
	int tmp;
	for(auto [v,w] : adj[u]){
		if(parent!=v){
		dfs(v,u);
	   tmp=max(f[v][0],f[v][1]+w);
		f[u][0]+=tmp;
		tp[u].insert(f[v][0]+w-tmp);
	   }
	}
	if(tp[u].empty()) f[u][1]=-inf;
	else f[u][1]=f[u][0] + *rbegin(tp[u]);
}
void dp(int u,int parent){
	int f_u[2],f_v[2],tmp,numv,numu;
	memcpy(f_u,f[u],8);
	ans=max(ans,f[u][0]);
	for(auto [v,w]:adj[u]){
		if(v!=parent){
			f[u][0]-=tmp=max(f[v][0],f[v][1]+w);
			numu=f[v][0]+w-tmp;
			tp[u].erase(tp[u].find(f[v][0]+w-tmp));
			f[u][1]=tp[u].empty()?-inf:f[u][0]+*rbegin(tp[u]);
			memcpy(f_v,f[v],8);
			f[v][0]+=tmp=max(f[u][0],f[u][1]+w);
			numv=f[u][0]+w-tmp;
			tp[v].insert(f[u][0]+w-tmp);
			f[v][1]=f[v][0]+ *rbegin(tp[v]);
			dp(v,u);
			memcpy(f[u],f_u,8);
			memcpy(f[v],f_v,8);
			tp[u].insert(numu);
			tp[v].erase(tp[v].find(numv));
		}
	}
}
void solve(){
//Sieve();
//   precal();
    cin>>n;
    for(int i=0;i<n-1;++i){
    	int u,v,w;
    	cin>>u>>v>>w;
    	adj[u].push_back({v,w});
    	adj[v].push_back({u,w});
	}
  dfs(1,0);
  dp(1,0);
   cout<<ans<<endl;
}
signed main(){
  // freopen(".inp","r",stdin);
  // freopen(".out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int test;
	test=1;
	#ifdef multipletest
	cin>>test;
	#endif
	while(test--){
        solve();
        #ifdef DEBUG
		cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
	    #endif
	}
}

Compilation message

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:114:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |  for(auto [v,w] : adj[u]){
      |           ^
beads.cpp: In function 'void dp(long long int, long long int)':
beads.cpp:129:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |  for(auto [v,w]:adj[u]){
      |           ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 6 ms 14432 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 7 ms 14432 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14356 KB Output is correct
9 Correct 8 ms 14432 KB Output is correct
10 Correct 7 ms 14432 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 7 ms 14420 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 6 ms 14432 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 7 ms 14432 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14356 KB Output is correct
9 Correct 8 ms 14432 KB Output is correct
10 Correct 7 ms 14432 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 7 ms 14420 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 7 ms 14428 KB Output is correct
15 Correct 7 ms 14404 KB Output is correct
16 Correct 7 ms 14372 KB Output is correct
17 Correct 7 ms 14444 KB Output is correct
18 Correct 7 ms 14432 KB Output is correct
19 Correct 7 ms 14364 KB Output is correct
20 Correct 7 ms 14432 KB Output is correct
21 Correct 7 ms 14420 KB Output is correct
22 Correct 7 ms 14428 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 6 ms 14432 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 7 ms 14432 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14356 KB Output is correct
9 Correct 8 ms 14432 KB Output is correct
10 Correct 7 ms 14432 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 7 ms 14420 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 7 ms 14428 KB Output is correct
15 Correct 7 ms 14404 KB Output is correct
16 Correct 7 ms 14372 KB Output is correct
17 Correct 7 ms 14444 KB Output is correct
18 Correct 7 ms 14432 KB Output is correct
19 Correct 7 ms 14364 KB Output is correct
20 Correct 7 ms 14432 KB Output is correct
21 Correct 7 ms 14420 KB Output is correct
22 Correct 7 ms 14428 KB Output is correct
23 Correct 10 ms 14956 KB Output is correct
24 Correct 10 ms 14952 KB Output is correct
25 Correct 10 ms 14996 KB Output is correct
26 Correct 13 ms 15700 KB Output is correct
27 Correct 14 ms 15620 KB Output is correct
28 Correct 17 ms 15696 KB Output is correct
29 Correct 17 ms 15572 KB Output is correct
30 Correct 15 ms 15572 KB Output is correct
31 Correct 14 ms 16224 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 6 ms 14432 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 7 ms 14432 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14356 KB Output is correct
9 Correct 8 ms 14432 KB Output is correct
10 Correct 7 ms 14432 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 7 ms 14420 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 7 ms 14428 KB Output is correct
15 Correct 7 ms 14404 KB Output is correct
16 Correct 7 ms 14372 KB Output is correct
17 Correct 7 ms 14444 KB Output is correct
18 Correct 7 ms 14432 KB Output is correct
19 Correct 7 ms 14364 KB Output is correct
20 Correct 7 ms 14432 KB Output is correct
21 Correct 7 ms 14420 KB Output is correct
22 Correct 7 ms 14428 KB Output is correct
23 Correct 10 ms 14956 KB Output is correct
24 Correct 10 ms 14952 KB Output is correct
25 Correct 10 ms 14996 KB Output is correct
26 Correct 13 ms 15700 KB Output is correct
27 Correct 14 ms 15620 KB Output is correct
28 Correct 17 ms 15696 KB Output is correct
29 Correct 17 ms 15572 KB Output is correct
30 Correct 15 ms 15572 KB Output is correct
31 Correct 14 ms 16224 KB Output is correct
32 Correct 49 ms 20808 KB Output is correct
33 Correct 51 ms 20784 KB Output is correct
34 Correct 46 ms 20812 KB Output is correct
35 Correct 285 ms 40684 KB Output is correct
36 Correct 291 ms 40616 KB Output is correct
37 Correct 263 ms 40708 KB Output is correct
38 Correct 310 ms 40028 KB Output is correct
39 Correct 294 ms 39852 KB Output is correct
40 Correct 277 ms 39960 KB Output is correct
41 Correct 290 ms 47300 KB Output is correct