Submission #1269566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269566		farica	Min-max tree (BOI18_minmaxtree)	C++20	0 / 100	142 ms	18872 KiB

minmaxtree

#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
 
const int MOD = 1e9;
/* 
template<ll mod>
struct modnum {
	static constexpr bool is_big_mod = mod > numeric_limits<int>::max();
 
	using S = conditional_t<is_big_mod, ll, int>;
	using L = conditional_t<is_big_mod, __int128, ll>;
 
	S x;
 
	modnum() : x(0) {}
	modnum(ll _x) {
		_x %= static_cast<ll>(mod);
		if (_x < 0) { _x += mod; }
		x = _x;
	}
 
	modnum pow(ll n) const {
		modnum res = 1;
		modnum cur = *this;
		while (n > 0) {
			if (n & 1) res *= cur;
			cur *= cur;
						n /= 2;
		}
		return res;
	}
	modnum inv() const { return (*this).pow(mod-2); }
 
	modnum& operator+=(const modnum& a){
		x += a.x;
		if (x >= mod) x -= mod;
		return *this;
	}
	modnum& operator-=(const modnum& a){
		if (x < a.x) x += mod;
		x -= a.x;
		return *this;
	}
	modnum& operator*=(const modnum& a){
		x = static_cast<L>(x) * a.x % mod;
		return *this;
	}
	modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
 
	friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
	friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
	friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
	friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
 
	friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
	friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
	friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }
 
	friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
	friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};
 
using mint = modnum<MOD>;
 
template <class T> class SumSegmentTree {
  private:
	const T DEFAULT = 0;

	vector<T> segtree;
	int len;

  public:
	SumSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}

	void set(int ind, T val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = segtree[ind] + segtree[ind ^ 1];
		}
	}

	T range_sum(int start, int end) {
		T sum = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { sum += segtree[start++]; }
			if (end % 2 == 1) { sum += segtree[--end]; }
		}
		return sum;
	}
};
 
struct DSU{
	vector<int> p, sz, used, mn, mx;
 
	DSU(int n){
		p.assign(n, 0);
		sz.assign(n, 1);
		used.assign(n, 0);
		mx.assign(n, 0);
		mn.assign(n, 0);
 
		for (int i = 0; i < n; i++) p[i] = i;
	}
 
	int find(int u){
		if (p[u] == u) return u;
		p[u] = find(p[u]);
		return p[u];
	}
		void unite(int u, int v){
		u = find(u);
		v = find(v);
		if (u == v) return;
 
		if (sz[u] < sz[v]) swap(u, v);
		p[v] = u;
		sz[u] += sz[v];
		used[u] += used[v];
		mn[u] = min(mn[u], mn[v]);
		mx[u] = max(mx[u], mx[v]);
	}
 
	bool same(int u, int v){
		return find(u) == find(v);
	}
 
	int size(int u){
		u = find(u);
		return sz[u];
	}
};

const int N = 250005;

struct BIT {
  ll b[N], n;
  
  void init(int _n) {
	n = _n ;
	for(int i = 0 ; i <= n ; ++i) b[i] = 0;
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, ll v) {
	for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  ll query(int x) {
	ll ans = 0;
	for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
	return ans;
  }
} bit[2]; */

int gcd(int a, int b, int& x, int& y) { // x*a + y*b = a1 
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

int inv_ecd(int a, int m) {
	int x, y;
	int g = gcd(a, m, x, y);
	if(g != 1) return -1;
	x = (x + m) % m;
	return x;
}

const int N = 70000;
const int LOG = 15;

vector<vector<pi>>adjL, edges;
vi w, in, dep;
int e, up[N][LOG];

void build(int pos, int prev=0) {
	in[pos] = e++;
	up[pos][0] = prev;
	for(int i=1; i<LOG; ++i) up[pos][i] = up[up[pos][i-1]][i-1];
	for(pi adj: adjL[pos]) {
		if(adj.first == prev) continue;
		dep[adj.first] = dep[pos] + 1;
		build(adj.first, pos);
	}
}

int LCA(int u, int v) {
	if(dep[u] > dep[v]) swap(u,v);
	for(int i=LOG-1; i>=0; --i) {
		if(dep[up[v][i]] < dep[u]) continue;
		v = up[v][i];
	}
	if(v == u) return u;
	for(int i=LOG-1; i>=0; --i) {
		if(up[u][i] != up[v][i]) {
			u = up[u][i];
			v = up[v][i];
		}
	}
	return up[u][0];
}

void dfs(int pos, int prev, priority_queue<pi>&pq, int id=-1) {
	for(pi adj: adjL[pos]) {
		if(adj.first == prev) continue;
		dfs(adj.first, pos, pq, adj.second);
	}
	if(!pos) return;
	for(pi edge: edges[pos]) {
		pq.push({edge.second * -1, edge.first});
	}
	int mi = in[prev];
	while(!pq.empty()) {
		pi cur = pq.top();
		cur.first *= -1;
		if(in[cur.second] > in[mi]) {
			pq.pop();
			continue;
		}
		w[id] = cur.first;
		break;
	} 
}

void solve() {
	int n;
	cin >> n;
	adjL.assign(n, vector<pi>());
	edges.assign(n, vector<pi>());
	w.assign(n-1, 0);
	dep.assign(n, 0);
	vector<pi>tmp(n);
	for(int i=0; i<n-1; ++i) {
		int u,v;
		cin >> u >> v;
		tmp[i] = {u,v};
		--u, --v;
		adjL[u].push_back({v, i});
		adjL[v].push_back({u, i});
	}
	e = 0;
	in.resize(n);
	build(0);
	int k;
	cin >> k;
	for(int i=0; i<k; ++i) {
		char c;
		cin >> c;
		int u, v, z;
		cin >> u >> v >> z;
		--u, --v;
		if(in[u] > in[v]) swap(u, v);
		int lca = LCA(u,v);
		if(lca == u) edges[v].push_back({u, z});
		else {
			edges[v].push_back({lca,z});
			edges[u].push_back({lca,z});
		} 
	}
	priority_queue<pi>PQ;
	dfs(0, 0, PQ);
	for(int i=0; i<n-1; ++i) cout << tmp[i].first << " " << tmp[i].second << " " << w[i] << endl; 
}
 
int main(){
	//freopen("cbarn.in", "r", stdin);
	//freopen("cbarn.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int tc = 1;
	while (tc--) solve();	
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42