Submission #922110

#	Time	Username	Problem	Language	Result	Execution time	Memory
922110		lozergam	Designated Cities (JOI19_designated_cities)	C++17	Compilation error	0 ms	0 KiB

designated_cities

//#pragma GCC optimize("Ofast")

//#include <bits/stdc++.h>

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <set>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define lb lower_bound
#define ub upper_bound
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define bg(x) (x).begin()
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);

ll Sum(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a += b;
 return a % MOD;
}

ll Mul(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a *= b;
 return a % MOD;
}

ll Pow(ll a , ll b , ll MOD)
{
   ll res = 1;
   while(b)
   {
        if((b & 1))res = Mul(res , a , MOD);
     a = Mul(a , a , MOD);
     b >>= 1;
   }
   return res;
}

ll Min(ll a , ll b)
{
   if(a > b)return b;
   return a;
}

ll Max(ll a , ll b)
{
   if(a > b)return a;
   return b;
}

ll Ceil(ll a , ll b)
{
 if(a % b)return (a/b)+1;
 return a/b;
}

/////////////////////
//VALS
const ll maxn = 2e5;
const ll INF = 1e18;

ll n;
set<arr(3)> adj[maxn];
ll q;
ll barg;
ll par[maxn];
ll dp[maxn];
ll dp1;
ll root;
/////////////////////
//FUNCTIONS
void dfs_1_1(ll u, ll p)
{
	par[u] = p;
	
	for(auto v : adj[u])
	{
		if(v[0] == p)continue;
		
		dp1 += v[1];
		dfs_1_1(v[0], u);
	}
}

void dfs_1_2(ll u, ll val)
{
	for(auto v : adj[u])
	{
		if(v[0] == par[u])continue;
		//debug(u);
		//debug(v[0]);
		dp[1] = Min(dp[1], val - v[1] + v[2]);
		//debug(val - v[1] + v[2]);
		dfs_1_2(v[0], val - v[1] + v[2]);
	}
}

void compress(ll u)
{
	if(u != root and sz(adj[u]) == 2)
	{
		auto ch = (*adj[u].begin());
		auto p = (*adj[u].rbegin());
		
		if(ch[0] == par[u])
			swap(ch,p);
			
		par[ch[0]] = p[0];
		adj[ch[0]].erase(adj[ch[0]].find({u, ch[2], ch[1]}));
		adj[p[0]].erase(adj[p[0]].find({u, p[2], p[1]}));
		adj[p[0]].insert({ch[0], p[2]+ch[1], p[1]+ch[2]});
		adj[ch[0]].insert({p[0], p[1]+ch[2], p[2]+ch[1]});	
	}
	
	for(auto v : adj[u])
		if(v[0] != par[u])
			compress(v[0]);
}
/////////////////////
//SOLVE
void solve()
{
	cin >> n;
	
	For(i,n-1)
	{
		ll a, b ,c ,d;
		cin >> a >> b >> c >> d;
		a--;
		b--;
		
		adj[a].insert({b,c,d});
		adj[b].insert({a,d,c});
	}
	
	barg = 0;
	For(i,n)if(sz(adj[i]) == 1)barg++;
			
	for(int i = barg; i <= n; i++)dp[i] = 0;
	
	root = 0;
	For(i,n)
		if(sz(adj[i]) != 1)
		{
			root = i;
			break;
		}
	
	dfs_1_1(root, root);
	dp[1] = dp1;
	//debug(dp[1]);	
	dfs_1_2(root, dp1);
	
												
	compress(root);
	
	set<arr(3)> s;
	
	For(i,n)
		if(sz(adj[i]) == 1)
		{
			auto u = (*adj[i].begin());
			s.insert({u[2],u[1], i});
		}
	/*
	debug(sz(s));
	for(auto u : s)
	{
		debug(u[0]);
		debug(u[1]);
		debug(u[2]);
		cout << "AAAAAA\n" << flush;
	}
	*/
		
	ll cur = 0;
	barg--;	
	
	//debug(barg);
/*
6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
100
2	
*/
	for(int i = barg; i >= 2; i--)
	{
		//cout <<"AAAAAAA\n" << flush;
		auto bst = (*s.begin());
		s.erase(bst);
		//debug(bst[0]);
		//debug(bst[1]);
		//debug(bst[2]);
		cur += bst[0];
		dp[i] = cur;
		
		//bst -> {0 -> bottom to top, 1 -> top to bottom, 2 -> index}
		//cout << "BF\n" << flush;
		adj[par[bst[2]]].erase(adj[par[bst[2]]].find({bst[2], bst[0], bst[1]}));
		//cout << "AF\n" << flush;
		if(i != 1 and sz(adj[par[bst[2]]]) == 2 and par[bst[2]] != root)
		{
			//cout << ":P\n" << flush;
			ll u = par[bst[2]];
			auto ch = (*adj[u].begin());
			auto p = (*adj[u].rbegin());
		
			if(ch[0] == par[u])
				swap(ch,p);
			
			par[ch[0]] = p[0];
			adj[ch[0]].erase(adj[ch[0]].find({u, ch[2], ch[1]}));//
			adj[p[0]].erase(adj[p[0]].find({u, p[2], p[1]}));
			adj[p[0]].insert({ch[0], p[2]+ch[1], p[1]+ch[2]});
			adj[ch[0]].insert({p[0], p[1]+ch[2], p[2]+ch[1]});
			
			s.erase(s.find({ch[1], ch[2], u}));
			s.insert({p[2]+ch[1], p[1]+ch[2], p[0]});
		}
		//cout << ";l\n" << flush;
	}
	
	cin >> q;
	
	while(q--)
	{
		//cout << "@_@\n" << endl;
		ll e;
		cin >> e;
		
		cout << dp[e] << endl;	
	}
}
/////////////////////
//MAIN
int main()
{
    FAST;
    ll t = 1;
//    cin >> t;
    while(t--)
    {
        solve();
    }
}
/////////////////////
/*
ZZZZZZZ     A        M     M     IIIIIII  N     N
     Z     A A      M M   M M       I     NN    N
    Z     A   A    M   M M   M      I     N N   N
   Z     AAAAAAA  M     M     M     I     N  N  N
  Z      A     A  M           M     I     N   N N
 Z       A     A  M           M     I     N    NN
ZZZZZZZ  A     A  M           M  IIIIIII  N     N  TREE
*///#pragma GCC optimize("Ofast")

//#include <bits/stdc++.h>

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <set>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define lb lower_bound
#define ub upper_bound
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define bg(x) (x).begin()
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);

ll Sum(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a += b;
 return a % MOD;
}

ll Mul(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a *= b;
 return a % MOD;
}

ll Pow(ll a , ll b , ll MOD)
{
   ll res = 1;
   while(b)
   {
        if((b & 1))res = Mul(res , a , MOD);
     a = Mul(a , a , MOD);
     b >>= 1;
   }
   return res;
}

ll Min(ll a , ll b)
{
   if(a > b)return b;
   return a;
}

ll Max(ll a , ll b)
{
   if(a > b)return a;
   return b;
}

ll Ceil(ll a , ll b)
{
 if(a % b)return (a/b)+1;
 return a/b;
}

/////////////////////
//VALS
const ll maxn = 2e5;
const ll INF = 1e18;

ll n;
set<arr(3)> adj[maxn];
ll q;
ll barg;
ll par[maxn];
ll dp[maxn];
ll dp1;
ll root;
/////////////////////
//FUNCTIONS
void dfs_1_1(ll u, ll p)
{
	par[u] = p;
	
	for(auto v : adj[u])
	{
		if(v[0] == p)continue;
		
		dp1 += v[1];
		dfs_1_1(v[0], u);
	}
}

void dfs_1_2(ll u, ll val)
{
	for(auto v : adj[u])
	{
		if(v[0] == par[u])continue;
		//debug(u);
		//debug(v[0]);
		dp[1] = Min(dp[1], val - v[1] + v[2]);
		//debug(val - v[1] + v[2]);
		dfs_1_2(v[0], val - v[1] + v[2]);
	}
}

void compress(ll u)
{
	if(u != root and sz(adj[u]) == 2)
	{
		auto ch = (*adj[u].begin());
		auto p = (*adj[u].rbegin());
		
		if(ch[0] == par[u])
			swap(ch,p);
			
		par[ch[0]] = p[0];
		adj[ch[0]].erase(adj[ch[0]].find({u, ch[2], ch[1]}));
		adj[p[0]].erase(adj[p[0]].find({u, p[2], p[1]}));
		adj[p[0]].insert({ch[0], p[2]+ch[1], p[1]+ch[2]});
		adj[ch[0]].insert({p[0], p[1]+ch[2], p[2]+ch[1]});	
	}
	
	for(auto v : adj[u])
		if(v[0] != par[u])
			compress(v[0]);
}
/////////////////////
//SOLVE
void solve()
{
	cin >> n;
	
	For(i,n-1)
	{
		ll a, b ,c ,d;
		cin >> a >> b >> c >> d;
		a--;
		b--;
		
		adj[a].insert({b,c,d});
		adj[b].insert({a,d,c});
	}
	
	barg = 0;
	For(i,n)if(sz(adj[i]) == 1)barg++;
			
	for(int i = barg; i <= n; i++)dp[i] = 0;
	
	root = 0;
	For(i,n)
		if(sz(adj[i]) != 1)
		{
			root = i;
			break;
		}
	
	dfs_1_1(root, root);
	dp[1] = dp1;
	//debug(dp[1]);	
	dfs_1_2(root, dp1);
	
												
	compress(root);
	
	set<arr(3)> s;
	
	For(i,n)
		if(sz(adj[i]) == 1)
		{
			auto u = (*adj[i].begin());
			s.insert({u[2],u[1], i});
		}
	/*
	debug(sz(s));
	for(auto u : s)
	{
		debug(u[0]);
		debug(u[1]);
		debug(u[2]);
		cout << "AAAAAA\n" << flush;
	}
	*/
		
	ll cur = 0;
	barg--;	
	
	//debug(barg);
/*
6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
100
2	
*/
	for(int i = barg; i >= 2; i--)
	{
		//cout <<"AAAAAAA\n" << flush;
		auto bst = (*s.begin());
		s.erase(bst);
		//debug(bst[0]);
		//debug(bst[1]);
		//debug(bst[2]);
		cur += bst[0];
		dp[i] = cur;
		
		//bst -> {0 -> bottom to top, 1 -> top to bottom, 2 -> index}
		//cout << "BF\n" << flush;
		adj[par[bst[2]]].erase(adj[par[bst[2]]].find({bst[2], bst[0], bst[1]}));
		//cout << "AF\n" << flush;
		if(i != 1 and sz(adj[par[bst[2]]]) == 2 and par[bst[2]] != root)
		{
			//cout << ":P\n" << flush;
			ll u = par[bst[2]];
			auto ch = (*adj[u].begin());
			auto p = (*adj[u].rbegin());
		
			if(ch[0] == par[u])
				swap(ch,p);
			
			par[ch[0]] = p[0];
			adj[ch[0]].erase(adj[ch[0]].find({u, ch[2], ch[1]}));//
			adj[p[0]].erase(adj[p[0]].find({u, p[2], p[1]}));
			adj[p[0]].insert({ch[0], p[2]+ch[1], p[1]+ch[2]});
			adj[ch[0]].insert({p[0], p[1]+ch[2], p[2]+ch[1]});
			
			s.erase(s.find({ch[1], ch[2], u}));
			s.insert({p[2]+ch[1], p[1]+ch[2], p[0]});
		}
		//cout << ";l\n" << flush;
	}
	
	cin >> q;
	
	while(q--)
	{
		//cout << "@_@\n" << endl;
		ll e;
		cin >> e;
		
		cout << dp[e] << endl;	
	}
}
/////////////////////
//MAIN
int main()
{
    FAST;
    ll t = 1;
//    cin >> t;
    while(t--)
    {
        solve();
    }
}
/////////////////////
/*
ZZZZZZZ     A        M     M     IIIIIII  N     N
     Z     A A      M M   M M       I     NN    N
    Z     A   A    M   M M   M      I     N N   N
   Z     AAAAAAA  M     M     M     I     N  N  N
  Z      A     A  M           M     I     N   N N
 Z       A     A  M           M     I     N    NN
ZZZZZZZ  A     A  M           M  IIIIIII  N     N  TREE
*/

Compilation message (stderr)

designated_cities.cpp: In function 'void solve()':
designated_cities.cpp:26:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
designated_cities.cpp:148:2: note: in expansion of macro 'For'
  148 |  For(i,n-1)
      |  ^~~
designated_cities.cpp:26:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
designated_cities.cpp:160:2: note: in expansion of macro 'For'
  160 |  For(i,n)if(sz(adj[i]) == 1)barg++;
      |  ^~~
designated_cities.cpp:26:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
designated_cities.cpp:165:2: note: in expansion of macro 'For'
  165 |  For(i,n)
      |  ^~~
designated_cities.cpp:26:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
designated_cities.cpp:182:2: note: in expansion of macro 'For'
  182 |  For(i,n)
      |  ^~~
designated_cities.cpp: At global scope:
designated_cities.cpp:315:4: error: redefinition of 'long long int Sum(long long int, long long int, long long int)'
  315 | ll Sum(ll a , ll b , ll MOD)
      |    ^~~
designated_cities.cpp:34:4: note: 'long long int Sum(long long int, long long int, long long int)' previously defined here
   34 | ll Sum(ll a , ll b , ll MOD)
      |    ^~~
designated_cities.cpp:323:4: error: redefinition of 'long long int Mul(long long int, long long int, long long int)'
  323 | ll Mul(ll a , ll b , ll MOD)
      |    ^~~
designated_cities.cpp:42:4: note: 'long long int Mul(long long int, long long int, long long int)' previously defined here
   42 | ll Mul(ll a , ll b , ll MOD)
      |    ^~~
designated_cities.cpp:331:4: error: redefinition of 'long long int Pow(long long int, long long int, long long int)'
  331 | ll Pow(ll a , ll b , ll MOD)
      |    ^~~
designated_cities.cpp:50:4: note: 'long long int Pow(long long int, long long int, long long int)' previously defined here
   50 | ll Pow(ll a , ll b , ll MOD)
      |    ^~~
designated_cities.cpp:343:4: error: redefinition of 'long long int Min(long long int, long long int)'
  343 | ll Min(ll a , ll b)
      |    ^~~
designated_cities.cpp:62:4: note: 'long long int Min(long long int, long long int)' previously defined here
   62 | ll Min(ll a , ll b)
      |    ^~~
designated_cities.cpp:349:4: error: redefinition of 'long long int Max(long long int, long long int)'
  349 | ll Max(ll a , ll b)
      |    ^~~
designated_cities.cpp:68:4: note: 'long long int Max(long long int, long long int)' previously defined here
   68 | ll Max(ll a , ll b)
      |    ^~~
designated_cities.cpp:355:4: error: redefinition of 'long long int Ceil(long long int, long long int)'
  355 | ll Ceil(ll a , ll b)
      |    ^~~~
designated_cities.cpp:74:4: note: 'long long int Ceil(long long int, long long int)' previously defined here
   74 | ll Ceil(ll a , ll b)
      |    ^~~~
designated_cities.cpp:363:10: error: redefinition of 'const long long int maxn'
  363 | const ll maxn = 2e5;
      |          ^~~~
designated_cities.cpp:82:10: note: 'const long long int maxn' previously defined here
   82 | const ll maxn = 2e5;
      |          ^~~~
designated_cities.cpp:364:10: error: redefinition of 'const long long int INF'
  364 | const ll INF = 1e18;
      |          ^~~
designated_cities.cpp:83:10: note: 'const long long int INF' previously defined here
   83 | const ll INF = 1e18;
      |          ^~~
designated_cities.cpp:366:4: error: redefinition of 'long long int n'
  366 | ll n;
      |    ^
designated_cities.cpp:85:4: note: 'long long int n' previously declared here
   85 | ll n;
      |    ^
designated_cities.cpp:367:13: error: redefinition of 'std::set<std::array<long long int, 3> > adj [200000]'
  367 | set<arr(3)> adj[maxn];
      |             ^~~
designated_cities.cpp:86:13: note: 'std::set<std::array<long long int, 3> > adj [200000]' previously declared here
   86 | set<arr(3)> adj[maxn];
      |             ^~~
designated_cities.cpp:368:4: error: redefinition of 'long long int q'
  368 | ll q;
      |    ^
designated_cities.cpp:87:4: note: 'long long int q' previously declared here
   87 | ll q;
      |    ^
designated_cities.cpp:369:4: error: redefinition of 'long long int barg'
  369 | ll barg;
      |    ^~~~
designated_cities.cpp:88:4: note: 'long long int barg' previously declared here
   88 | ll barg;
      |    ^~~~
designated_cities.cpp:370:4: error: redefinition of 'long long int par [200000]'
  370 | ll par[maxn];
      |    ^~~
designated_cities.cpp:89:4: note: 'long long int par [200000]' previously declared here
   89 | ll par[maxn];
      |    ^~~
designated_cities.cpp:371:4: error: redefinition of 'long long int dp [200000]'
  371 | ll dp[maxn];
      |    ^~
designated_cities.cpp:90:4: note: 'long long int dp [200000]' previously declared here
   90 | ll dp[maxn];
      |    ^~
designated_cities.cpp:372:4: error: redefinition of 'long long int dp1'
  372 | ll dp1;
      |    ^~~
designated_cities.cpp:91:4: note: 'long long int dp1' previously declared here
   91 | ll dp1;
      |    ^~~
designated_cities.cpp:373:4: error: redefinition of 'long long int root'
  373 | ll root;
      |    ^~~~
designated_cities.cpp:92:4: note: 'long long int root' previously declared here
   92 | ll root;
      |    ^~~~
designated_cities.cpp:376:6: error: redefinition of 'void dfs_1_1(long long int, long long int)'
  376 | void dfs_1_1(ll u, ll p)
      |      ^~~~~~~
designated_cities.cpp:95:6: note: 'void dfs_1_1(long long int, long long int)' previously defined here
   95 | void dfs_1_1(ll u, ll p)
      |      ^~~~~~~
designated_cities.cpp:389:6: error: redefinition of 'void dfs_1_2(long long int, long long int)'
  389 | void dfs_1_2(ll u, ll val)
      |      ^~~~~~~
designated_cities.cpp:108:6: note: 'void dfs_1_2(long long int, long long int)' previously defined here
  108 | void dfs_1_2(ll u, ll val)
      |      ^~~~~~~
designated_cities.cpp:402:6: error: redefinition of 'void compress(long long int)'
  402 | void compress(ll u)
      |      ^~~~~~~~
designated_cities.cpp:121:6: note: 'void compress(long long int)' previously defined here
  121 | void compress(ll u)
      |      ^~~~~~~~
designated_cities.cpp:425:6: error: redefinition of 'void solve()'
  425 | void solve()
      |      ^~~~~
designated_cities.cpp:144:6: note: 'void solve()' previously defined here
  144 | void solve()
      |      ^~~~~
designated_cities.cpp: In function 'void solve()':
designated_cities.cpp:307:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
  307 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
designated_cities.cpp:429:2: note: in expansion of macro 'For'
  429 |  For(i,n-1)
      |  ^~~
designated_cities.cpp:307:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
  307 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
designated_cities.cpp:441:2: note: in expansion of macro 'For'
  441 |  For(i,n)if(sz(adj[i]) == 1)barg++;
      |  ^~~
designated_cities.cpp:307:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
  307 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
designated_cities.cpp:446:2: note: in expansion of macro 'For'
  446 |  For(i,n)
      |  ^~~
designated_cities.cpp:307:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
  307 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
designated_cities.cpp:463:2: note: in expansion of macro 'For'
  463 |  For(i,n)
      |  ^~~
designated_cities.cpp: At global scope:
designated_cities.cpp:544:5: error: redefinition of 'int main()'
  544 | int main()
      |     ^~~~
designated_cities.cpp:263:5: note: 'int main()' previously defined here
  263 | int main()
      |     ^~~~