526互联

Kattis - A Complex Problem (The 2023 ICPC Rocky Mountain Regional Contest)

发布时间 2023-11-11 07:33:53作者: 祈雨ㅤ

Intro

This was one of the problems I didn't do during the regional contest. One of my teammates solved it.

Observation

There are few things to note.

  • First type of notation: subset means that A $ \subset $ B, but there can be cases that subset forms a SCC s.t. all nodes in the SCC are same classification class.
  • Second type: this means A is different class from B, with 1 less problem. But consider a case A is both type2 to B and C, then B and C may or may not be the same thing. Therefore, the size of the class can be used to determine if they can be same or not. Which naturally leads to DP on DAG (which can be determined by topological sort).

Solution

Consider all type1 as edges with weight 0, all type2 as edges with weight 1. Run a SCC code to find all strongly connected components. The maximum possible number of classes = the number of SCC in the graph. Now we consider the minimum case. Since KACTL SCC code traverses the components in reverse topological sort order, we can do a linear scan from last component to the first to get a topological order. Having a dp table set up with size = # of components in the graph. Then we do a DP on DAG and the maximum value in the dp table is the minimal number of classification class we can have.

Remark

  • KACTL SCC code traverses in reverse topological order.
  • A single node is always a SCC.
  • Lambda Function is used for kactl scc.
[&](vi &v) {...}

Code

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vi val, comp, z, cont;
int Time, ncomps;
template<class G, class F> int dfs(int j, G& g, F& f) {
	int low = val[j] = ++Time, x; z.push_back(j);
	for (auto e : g[j]) if (comp[e] < 0)
		low = min(low, val[e] ?: dfs(e,g,f));

	if (low == val[j]) {
		do {
			x = z.back(); z.pop_back();
			comp[x] = ncomps;
			cont.push_back(x);
		} while (x != j);
		f(cont); cont.clear();
		ncomps++;
	}
	return val[j] = low;
}
template<class G, class F> void scc(G& g, F f) {
	int n = sz(g);
	val.assign(n, 0); comp.assign(n, -1);
	Time = ncomps = 0;
	rep(i,0,n) if (comp[i] < 0) dfs(i, g, f);
}

map<string, int> mp;
int N = 0;
int id(string s) {
    if (mp.count(s)) return mp[s];
    mp[s] = N++;
    return mp[s];
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> edges;
    rep(i, 0, n) {
        string a, b;
        cin >> a >> b;
        int u = id(a);
        int v = id(b);
        edges.pb({u, v, 0});
    }
    rep(i, 0, m) {
        string a, b;
        cin >> a >> b;
        int u = id(a);
        int v = id(b);
        edges.pb({u, v, 1});
    }
    vector<vi> adj(N);
    for (auto &[a, b, _] : edges) {
        adj[a].pb(b);
    }
    scc(adj, [&](vi &v){return;});
    vector<vector<pii>> t_adj(N);

    for (auto &[a, b, _] : edges) {
        if (comp[a] == comp[b]) continue;
        t_adj[comp[a]].pb({comp[b], _});
    }

    vi ans(ncomps, -1);
    int mn = 0;
    for (int i = ncomps -1; i >= 0; i--) {
        if (ans[i] == -1) ans[i] = 1;
        mn = max(mn, ans[i]);
        for (auto &[b, kind] : t_adj[i]) {
            int cand = ans[i] + kind;
            ans[b] = max(ans[b], cand);
        }
    }
    cout << mn << ' ' << ncomps << '\n';
    return 0;
}