Submission #1240781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240781		MateiKing80	Min-max tree (BOI18_minmaxtree)	C++20	0 / 100	183 ms	42808 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

vector<pair<int, int>> rasps;
int cn;

struct Dinic {
    int n;
    struct EDGE {
        int from, to, cap, prev;
    };
    vector<EDGE> edges;
    vector<int> dist, last, fakeLast;
    Dinic (int _n) {
        n = _n + 1;
        last.resize(n, -1);
        dist.resize(n);
    }
    void addEdge(int u, int v, int c) {
        edges.push_back({u, v, c, last[u]});
        last[u] = edges.size() - 1;
        edges.push_back({v, u, 0, last[v]});
        last[v] = edges.size() - 1;
    }
    bool bfs(int s, int d) {
        dist.assign(n, inf);
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int i = last[x]; i != -1; i = edges[i].prev) {
                if (edges[i].cap && dist[edges[i].to] == inf) {
                    dist[edges[i].to] = dist[x] + 1;
                    q.push(edges[i].to);
                }
            }
        }
        fakeLast = last;
        return dist[d] != inf;
    }
    int dfs(int nod, int d, int push) {
        if (push == 0)
            return 0;
        if (nod == d)
            return push;
        int ans = 0;
        for (int i = fakeLast[nod]; i != -1; i = edges[i].prev) {
            if (push == 0)
                break;
            fakeLast[nod] = i;
            if (dist[edges[i].to] > dist[nod] && edges[i].cap) {
                int x = dfs(edges[i].to, d, min(push, edges[i].cap));
                push -= x;
                ans += x;
                edges[i].cap -= x;
                edges[i ^ 1].cap += x;
            }
        }
        return ans;
    }
    int maxFlow(int s, int d) {
        int ans = 0;
        while (bfs(s, d))
            ans += dfs(s, d, inf);
        return ans;
    }
    void skib(int s, int d) {
		 maxFlow(s, d);
		 for (int i = 0; i < (int)edges.size(); i += 2) {
			 if (2 <= edges[i].to && edges[i].to <= cn && edges[i].cap == 0) {
				 rasps.push_back({edges[i].to, edges[i].from});
			 }
		 }
	 }
};

const int N = 70005;
vector<int> vec[N];

vector<int> lazyMare[N], lazyMic[N];
set<int> setMare[N], setMic[N];
int lift[20][N], depth[N], mare[N], mic[N];

void dfs(int nod, int papa) {
	depth[nod] = 1 + depth[papa];
	lift[0][nod] = papa;
	for (int bit = 1; bit < 20; bit ++)
		lift[bit][nod] = lift[bit - 1][lift[bit - 1][nod]];
	for (auto i : vec[nod])
		if (i != papa)
			dfs(i, nod);
}

int lca(int x, int y) {
	if (depth[x] > depth[y])
		swap(x, y);
	for (int bit = 19; bit >= 0; bit --)
		if (depth[lift[bit][y]] >= x)
			y = lift[bit][y];
	if (x == y)
		return x;
	for (int bit = 19; bit >= 0; bit --)
		if (lift[bit][x] != lift[bit][y]) {
			x = lift[bit][x];
			y = lift[bit][y];
		}
	return lift[0][x];
}

void dfsMare(int nod, int papa) {
	int fmax = 0;
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		dfsMare(i, nod);
		if (setMare[i].size() >= setMare[fmax].size())
			fmax = i;
	}
	swap(setMare[fmax], setMare[nod]);
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		for (auto j : setMare[i])
			setMare[nod].insert(j);
		setMare[i].clear();
	}
	for (auto i : lazyMare[nod]) {
		if (i < 0)
			setMare[nod].erase(-i);
		else
			setMare[nod].insert(i);
	}
	if (setMare[nod].empty())
		mare[nod] = -1;
	else
		mare[nod] = *setMare[nod].rbegin();
}

void dfsMic(int nod, int papa) {
	int fmax = 0;
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		dfsMic(i, nod);
		if (setMic[i].size() >= setMic[fmax].size())
			fmax = i;
	}
	swap(setMic[fmax], setMic[nod]);
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		for (auto j : setMic[i])
			setMic[nod].insert(j);
		setMic[i].clear();
	}
	for (auto i : lazyMic[nod]) {
		if (i < 0)
			setMic[nod].erase(-i);
		else
			setMic[nod].insert(i);
	}
	if (setMic[nod].empty())
		mic[nod] = -1;
	else
		mic[nod] = *setMic[nod].begin();
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	cn = n;
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs(1, 0);
	int q;
	cin >> q;
	while (q --) {
		char ch;
		int x, y, z;
		cin >> ch >> x >> y >> z;
		if (ch == 'M') {
			lazyMare[x].push_back(z);
			lazyMare[y].push_back(z);
			lazyMare[lca(x, y)].push_back(-z);
		} else {
			lazyMic[x].push_back(z);
			lazyMic[y].push_back(z);
			lazyMic[lca(x, y)].push_back(-z);
		}
	}
	dfsMare(1, 0);
	dfsMic(1, 0);
	map<int, int> mp;
	map<int, int> remp;
	int cnt = n;
	Dinic ds(3 * n + 2);
	for (int i = 2; i <= n; i ++) {
		if (mare[i] != -1 && mp[mare[i]] == 0) {
			mp[mare[i]] = ++cnt;
			remp[cnt] = mare[i];
			ds.addEdge(0, mp[mare[i]], 1);
		}
		if (mic[i] != -1 && mp[mic[i]] == 0) {
			mp[mic[i]] = ++cnt;
			remp[cnt] = mic[i];
			ds.addEdge(0, mp[mic[i]], 1);
		}
	}
	for (int i = 2; i <= n; i ++) {
		if (mare[i] != -1)
			ds.addEdge(mp[mare[i]], i, 1);
		if (mic[i] != -1)
			ds.addEdge(mp[mic[i]], i, 1);
		ds.addEdge(i, 1, 1);
	}
	ds.skib(0, 1);
	vector<int> ans(n + 1, -1);
	for (auto i : rasps)
		ans[i.first] = remp[i.second];
	for (int i = 2; i <= n; i ++) {
		if (ans[i] == -1) {
			if (mic[i] != -1)
				ans[i] = mic[i];
			else if (mare[i] != -1)
				ans[i] = mare[i];
			else
				ans[i] = 69;
		}
	}
	for (int i = 2; i <= n; i ++)
		cout << i << " " << lift[0][i] << " " << ans[i] << '\n';
}

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