oj.uz

Submission #943744

# Submission time Handle Problem Language Result Execution time Memory
943744 2024-03-11T19:45:20 Z shadow_sami Factories (JOI14_factories) C++17
100 / 100
 3799 ms 375068 KB 
#include"factories.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
// typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
vector<pi> adj[mx];
vector<pi> lis[mx];
ll sz[mx];
bool mark[mx];
ll pd[mx];

void dfs2(ll u,ll par){
	sz[u] = 1;
	fx(adj[u])
		if(x.ff!=par && !mark[x.ff]){
			dfs2(x.ff,u);
			sz[u] += sz[x.ff];
		}
	return;
}

ll find(ll u,ll par,ll p){
	fx(adj[u])
		if(x.ff!=par && !mark[x.ff]){
			if(sz[x.ff]*2>sz[p])
				return find(x.ff,u,p);
		}
	return u;
}

void dfs3(ll u,ll par,ll d,ll p){
	lis[u].push_back({p,d});
	fx(adj[u])
		if(x.ff!=par && !mark[x.ff]){
			dfs3(x.ff,u,d+x.ss,p);
		}
	return;
}

void divide(ll u){
	dfs2(u,-1);
	u = find(u,-1,u);
	// debug(u);
	mark[u] = 1;
	lis[u].push_back({u,0});
	fx(adj[u])
		if(!mark[x.ff])
			dfs3(x.ff,u,x.ss,u);
	fx(adj[u])
		if(!mark[x.ff])
			divide(x.ff);
}

void Init(int N, int A[], int B[], int D[]){
	n = N;
	fip(0,n-1){
		A[i]++;
		B[i]++;
		adj[A[i]].push_back({B[i],D[i]});
		adj[B[i]].push_back({A[i],D[i]});
	}
	divide(1);
	// fip(1,n+1){
	// 	debug(lis[i]);
	// }		
	fip(1,n+1)
		pd[i] = 1e18;
	return;
}

void update(ll u){
	// debug(lis[u]);
	fx(lis[u])
		pd[x.ff] = min(pd[x.ff],x.ss);
	return;
}

void query(ll u){
	fx(lis[u])
		ans = min(ans,x.ss+pd[x.ff]);
	return;
}

void rollback(ll u){
	fx(lis[u])
		pd[x.ff] = 1e18;
	return;
}

long long Query(int S, int X[], int T, int Y[]) {
	fip(0,S){
		X[i]++;
		update(X[i]);
	}
	ans = 1e18;	
	fip(0,T){
		Y[i]++;
		query(Y[i]);
	}
	fip(0,S)
		rollback(X[i]);
  return ans;
}

/*int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input1.txt", "r", stdin);
        freopen("output1.txt", "w", stdout);
        freopen("error1.txt", "w", stderr);
    #endif // ONLINE_JUDGE

        int N,M;
        cin>>N>>M;
        int A[N-1],B[N-1],D[N-1];
        fip(0,N-1)
        	cin>>A[i]>>B[i]>>D[i];                        
        Init(N,A,B,D);
        fip(0,M){
        	int S,T;        	
        	cin>>S;
        	cin>>T;
        	int X[S];        	
        	fip(0,S)
        		cin>>X[i];        	
        	int Y[T];
        	fip(0,T)
        		cin>>Y[i];
        	cout<<Query(S,X,T,Y)<<nli;
        }
        
   // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 45656 KB Output is correct
2 Correct 204 ms 60128 KB Output is correct
3 Correct 212 ms 60720 KB Output is correct
4 Correct 220 ms 60500 KB Output is correct
5 Correct 229 ms 60908 KB Output is correct
6 Correct 156 ms 59752 KB Output is correct
7 Correct 216 ms 60500 KB Output is correct
8 Correct 207 ms 61004 KB Output is correct
9 Correct 240 ms 61068 KB Output is correct
10 Correct 171 ms 59752 KB Output is correct
11 Correct 213 ms 60676 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45660 KB Output is correct
2 Correct 1897 ms 226948 KB Output is correct
3 Correct 2744 ms 298136 KB Output is correct
4 Correct 638 ms 121052 KB Output is correct
5 Correct 3263 ms 372464 KB Output is correct
6 Correct 2841 ms 298460 KB Output is correct
7 Correct 668 ms 100028 KB Output is correct
8 Correct 246 ms 76216 KB Output is correct
9 Correct 819 ms 113232 KB Output is correct
10 Correct 756 ms 100464 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 45656 KB Output is correct
2 Correct 204 ms 60128 KB Output is correct
3 Correct 212 ms 60720 KB Output is correct
4 Correct 220 ms 60500 KB Output is correct
5 Correct 229 ms 60908 KB Output is correct
6 Correct 156 ms 59752 KB Output is correct
7 Correct 216 ms 60500 KB Output is correct
8 Correct 207 ms 61004 KB Output is correct
9 Correct 240 ms 61068 KB Output is correct
10 Correct 171 ms 59752 KB Output is correct
11 Correct 213 ms 60676 KB Output is correct
12 Correct 9 ms 45660 KB Output is correct
13 Correct 1897 ms 226948 KB Output is correct
14 Correct 2744 ms 298136 KB Output is correct
15 Correct 638 ms 121052 KB Output is correct
16 Correct 3263 ms 372464 KB Output is correct
17 Correct 2841 ms 298460 KB Output is correct
18 Correct 668 ms 100028 KB Output is correct
19 Correct 246 ms 76216 KB Output is correct
20 Correct 819 ms 113232 KB Output is correct
21 Correct 756 ms 100464 KB Output is correct
22 Correct 2164 ms 229584 KB Output is correct
23 Correct 2180 ms 233424 KB Output is correct
24 Correct 3296 ms 302308 KB Output is correct
25 Correct 3310 ms 304720 KB Output is correct
26 Correct 3192 ms 303424 KB Output is correct
27 Correct 3799 ms 375068 KB Output is correct
28 Correct 826 ms 127112 KB Output is correct
29 Correct 3207 ms 303016 KB Output is correct
30 Correct 3114 ms 302996 KB Output is correct
31 Correct 3070 ms 302804 KB Output is correct
32 Correct 933 ms 113572 KB Output is correct
33 Correct 261 ms 76220 KB Output is correct
34 Correct 552 ms 93092 KB Output is correct
35 Correct 529 ms 94016 KB Output is correct
36 Correct 653 ms 98912 KB Output is correct
37 Correct 670 ms 98972 KB Output is correct