제출 #1260769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260769		namhh	Two Currencies (JOI23_currencies)	C++20	100 / 100	3219 ms	57284 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
const int lg = 17;
int n,m,q,sta[N],ed[N],bits[N][2],h[N],st[N][lg],l[N],r[N],ans[N],timer = 1;
pii canh[N],events[N];
vector<int>adj[N],emilia[N];
struct query{
	int u,v,x,y;
};
query qr[N];
void update(int u, int type, int val){
	while(u <= n){
		bits[u][type] += val;
		u += u & (-u);
	}
}
int get(int u, int type){
	int sum = 0;
	while(u > 0){
		sum += bits[u][type];
		u -= u & (-u);
	}
	return sum;
}
void dfs(int u, int p){
	h[u] = h[p]+1;
	st[u][0] = p;
	sta[u] = timer;
	timer++;
	for(int i = 1; i < lg; i++) st[u][i] = st[st[u][i-1]][i-1];
	for(int v: adj[u]){
		if(v != p) dfs(v,u);
	}
	ed[u] = timer-1;
}
int lca(int u, int v){
	if(h[u] < h[v]) swap(u,v);
	for(int i = lg-1; i >= 0; i--){
		if(h[st[u][i]] >= h[v]) u = st[u][i];
	}
	if(u == v) return u;
	for(int i = lg-1; i >= 0; i--){
		if(st[u][i] != st[v][i]){
			u = st[u][i];
			v = st[v][i];
		}
	}
	return st[u][0];
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		cin >> canh[i].fi >> canh[i].se;
		adj[canh[i].fi].push_back(canh[i].se);
		adj[canh[i].se].push_back(canh[i].fi);
	}
	dfs(1,0);
	//for(int i = 1; i <= n; i++) cout << sta[i] << " " << ed[i] << "\n";
	for(int i = 1; i <= m; i++){
		cin >> events[i].fi >> events[i].se;
		swap(events[i].fi,events[i].se);
	}
	sort(events+1,events+m+1);
	for(int i = 1; i <= q; i++){
		cin >> qr[i].u >> qr[i].v >> qr[i].x >> qr[i].y;
		l[i] = 1;
		r[i] = m;
	}
	while(true){
		int cnt = 0;
		for(int i = 1; i <= m; i++) emilia[i].clear();
		for(int i = 1; i <= q; i++){
			if(l[i] <= r[i]){
			    emilia[(l[i]+r[i])/2].push_back(i);
			    cnt++;
			}
		}
		if(cnt == 0) break;
		for(int i = 1; i <= n; i++){
			bits[i][0] = 0;
			bits[i][1] = 0;
		}
		for(int i = 1; i <= m; i++){
			int xx = canh[events[i].se].fi;
			int yy = canh[events[i].se].se;
			if(xx == st[yy][0]) swap(xx,yy);
			int x = sta[xx];
			int y = ed[xx]+1;
			//cout << xx << " " << x << " " << y << "\n";
			int val = events[i].fi;
			update(x,0,1);
			update(y,0,-1);
			update(x,1,val);
			update(y,1,-val);
			for(int v: emilia[i]){
				int u = qr[v].u;
				int vv = qr[v].v;
				int k = lca(u,vv);
				int sum1 = get(sta[u],0)+get(sta[vv],0)-2*get(sta[k],0);
				int sum2 = get(sta[u],1)+get(sta[vv],1)-2*get(sta[k],1);
				if(sum2 <= qr[v].y){
					ans[v] = sum1;
					l[v] = i+1;
				}
				else r[v] = i-1;
			}
		}
	}
	for(int i = 1; i <= q; i++){
		int u = qr[i].u;
		int v = qr[i].v;
	    int k = lca(u,v);
	    //cout << u << " " << v << " " << k << "\n";
	    int sum1 = get(sta[u],0)+get(sta[v],0)-2*get(sta[k],0);
	    //cout << sum1 << " ";
	    if(sum1 <= ans[i]+qr[i].x) cout << qr[i].x-max((int)0,sum1-ans[i]) << "\n";
	    else cout << -1 << "\n";
	}
}
//                                                                                                    
//                                +.::=.                   .*: -.                                     
//                               --    :.                 =  -:--                                     
//                               .=    ..  .-=++*+++=:.  =      :                                     
//                                .=   ....:=%@@@@@*:    .     :.                                     
//                            .-+=..:   :.  .+##%##+.  .:     .+:                                     
//                         :*@**%* ..   :.               ::..:.:. --:                                 
//             .--.      +@@@@@%:   .==:                         .###@*                               
//            :--  -:  -:@@@@#                   -                 =@@@@#. .=  : +                    
//            .:    -=--==:                      ==      +-          :*%*++=   .:#                    
//             -.     .:.           .             +.      -*.   =@@.   .-.      .=                    
//               +=..  ..          --             .*       .#. +@#      -      :==*=                  
//             .=.+=::::           =.              =-        ##@+        :--+.#@%++%*                 
//            .++@@:        =      +               .%%%%@@@@@@@@@@@@@@%.    :-@#-: -@.                
//           :@@@@=        .+     .=                *#     .#@.=-             =@::-:@:                
//          :-@@%.         --     --                :@*.  .%#   +.          -  ** :=%. .*@#           
//    :-.  .-*-.           -:     +.                 %-=::@#    .*   :      -  :%- +%.+@+@@           
// .- :.  **:     +:       =      #                : =* =@#      -=  #     #@@@:-@ :*@@. %@           
//  -=:      ::  .* .=     +      #                =..@  .*.      +. *.    *#=.+%@*-%*   %@           
//   :=. :.. .:  +. -=    .+      #                -- #.   =-     .+ +:    =@+   .+-++   @%           
//       ++-=.   *  --    :=      #                :- +-    :*     =:+:    -@#  :@#*%@@@%@+           
//       *.     --  --    :=      #                .= #@#=.   +-   :=+:    :%@-#@@@#@+:@@#            
//       +      +.  --    :=      #                .= :=       .+.  +*.     *@@+=@-=@*-.#@.           
//       =      +   :=    .+      #                 = .=         .#.-@.     -+ .%# -@@=  @#           
//      .=     .=   .+     +      *.                = .+..         :*@      == =@. -#@#: @%           
//      .=     .=    *     +      =:               .=.**:   =--:     #    * *- %*  =*=@+#@:           
//      .=     :=    #     =.     .+ .             .= --.#@@@@@#@@@: *   -= #..@=  **:@@@:            
//       +     .=    +:    --      + #             := +@%:@#: -:%= ===   #..* .#@@%@+.@@+             
//       *     .=    .*    .=      -:-=            :- #= ++  =- =@. *:  .* -*:  :  . .@@%             
//       *      +     *     +.     :- #            -- #  *: .@@  %- +   =- +-.- :.   .@@@.            
//       -:     =:    :=    .*      +.--           =:--  .*.:.:  # .=   +  *+    -   :@%@=            
//        +      *   *:+.    ==     .+ +.          +.#     .=-:=-  --  -- =+:    =   -@#%*            
//        +      -=   *==     *.     -=--         :+-=       :::   =:  +  %:.    =   %@+##            
//        .=      +:   +*-     +      +:+.        +:*.            .+  +: #.:. - .+  -@@=#%            
//         -.      =.  :=#-    :=      =:*    .-==#+-             +: =- +:-..- :%*  =@@:*%            
//         .-       +.  --+=           .**%+-:.                  -* +-:*:.:.  =@@* :-@@ *%            
//          -.       +=  -+==      -*#-          =-               ..        .%@#@=.--@* *%            
//           =.       .+: :+-*-=+:                                      +%+*@@%%@-= +@- *#            
//            -::=      :**=:                                          :@@@@@@%@@-  #@  #*            
//             -: +:       -                                          .@@#%@@%@@:  :@# .#+            
//              :- :#=     --                                        :@@@#@-=@#.   =@- .%=            
//                =:.@@%=   =#                   .+.=.              +@@@@* -*:     #%  :@:            
//                 .+ *@@@@@@@@*                                  :@@*@@@*        .@+  -@.            
//                   .+=%@*%@@@@@#:                             =@@@%:.:          +@:  +%             
//                     .=%@%#@@@@##@*:                       =%@@@#:              @#   ##             
//                         :#@%@@@@#@@@@+                 :*. @:                 =@-  .@+             
//                                 .+@%#%@@:=-..       .=:    %*==+.             @%   -@-             
//                                  =.    =:     :-:.::     .-- .= -:           =@-    -              
//                                 .-  :-. ::              .-     =-:                                 
//       .=+-.=-.*-                 =       -..+*:     .-:.-       =                  .+*#   ....     
//      =.         -=               -:      ..    -.  +.  -.      +.                -+   -*=:    +.   
//     .-            +-              *             -.*           #+               .+   =.        :=   
//     :-             --=*:        -+ *=           -#           -  -##+-..    .:+#:              +.   
//     :-             =    --=:==+*.    =:         .:     .=              =**=    =             .+    
//     .=             +     =--              :-          .=.               --    .-             =     
//      =             .-    --:               .-+*@%*#                     +.    +             :-     
//       +             +-   -:-           :*@@@@@@*@#*@@%*=:              =:    -              -.     
//       .*            -    ::+         =@@@@#-.-@@%%@@+=%@@@%=          -::   =              :-      
//        .+           :.    +-.       #@@@=   +@@@-#@@%.   +@@@+       .:=   .-             +:       
//         .--.         -.   :=-      :@@+   :@@@@# =@@@#     -%@#      -=    ::         :-+-         
//           * -         +    --.      +@@#=%@@@@@. :@@@@%     :%@     :=    =.          -=+          
//            .-**-      -.    --       .%@@@@+%@+   @@+%@@*-+@@@.    :=.   -          :+*-           
//                   :===-==.  .-=            *@%    *@= +%%##=.     :=:   :. .::-==-.                
//                           .::-=+=+=-:.     #%:    -#:           .-*#+===-:.                        
//                                           ..::---====---::.                              

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32