oj.uz

Submission #706651

# Submission time Handle Problem Language Result Execution time Memory
706651 2023-03-07T09:37:10 Z hoangnghiep Beads and wires (APIO14_beads) C++14
100 / 100
 320 ms 48124 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],sizeof(f[v]));
			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,sizeof(f_u));
			memcpy(f[v],f_v,sizeof(f_v));
			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 8 ms 14432 KB Output is correct
3 Correct 8 ms 14320 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14524 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14316 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14432 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 8 ms 14432 KB Output is correct
3 Correct 8 ms 14320 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14524 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14316 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14432 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 8 ms 14332 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Correct 7 ms 14336 KB Output is correct
18 Correct 7 ms 14324 KB Output is correct
19 Correct 7 ms 14420 KB Output is correct
20 Correct 7 ms 14420 KB Output is correct
21 Correct 7 ms 14380 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 8 ms 14432 KB Output is correct
3 Correct 8 ms 14320 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14524 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14316 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14432 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 8 ms 14332 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Correct 7 ms 14336 KB Output is correct
18 Correct 7 ms 14324 KB Output is correct
19 Correct 7 ms 14420 KB Output is correct
20 Correct 7 ms 14420 KB Output is correct
21 Correct 7 ms 14380 KB Output is correct
22 Correct 7 ms 14428 KB Output is correct
23 Correct 10 ms 15060 KB Output is correct
24 Correct 12 ms 14956 KB Output is correct
25 Correct 11 ms 15060 KB Output is correct
26 Correct 14 ms 15700 KB Output is correct
27 Correct 13 ms 15720 KB Output is correct
28 Correct 15 ms 15696 KB Output is correct
29 Correct 18 ms 15604 KB Output is correct
30 Correct 15 ms 15572 KB Output is correct
31 Correct 15 ms 16368 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 8 ms 14432 KB Output is correct
3 Correct 8 ms 14320 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14524 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14316 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14432 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 8 ms 14332 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Correct 7 ms 14336 KB Output is correct
18 Correct 7 ms 14324 KB Output is correct
19 Correct 7 ms 14420 KB Output is correct
20 Correct 7 ms 14420 KB Output is correct
21 Correct 7 ms 14380 KB Output is correct
22 Correct 7 ms 14428 KB Output is correct
23 Correct 10 ms 15060 KB Output is correct
24 Correct 12 ms 14956 KB Output is correct
25 Correct 11 ms 15060 KB Output is correct
26 Correct 14 ms 15700 KB Output is correct
27 Correct 13 ms 15720 KB Output is correct
28 Correct 15 ms 15696 KB Output is correct
29 Correct 18 ms 15604 KB Output is correct
30 Correct 15 ms 15572 KB Output is correct
31 Correct 15 ms 16368 KB Output is correct
32 Correct 49 ms 20876 KB Output is correct
33 Correct 53 ms 20840 KB Output is correct
34 Correct 54 ms 20880 KB Output is correct
35 Correct 263 ms 40672 KB Output is correct
36 Correct 276 ms 40696 KB Output is correct
37 Correct 273 ms 40672 KB Output is correct
38 Correct 320 ms 39972 KB Output is correct
39 Correct 302 ms 39772 KB Output is correct
40 Correct 293 ms 39972 KB Output is correct
41 Correct 310 ms 48124 KB Output is correct