Submission #734147

#	Time	Username	Problem	Language	Result	Execution time	Memory
734147		DrearyJoke	KOVANICE (COI15_kovanice)	C++17	100 / 100	337 ms	70840 KiB

kovanice

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define END "\n"
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#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);
}


void solve(){
    int n, m, V;
    cin >> n >> m >> V;
    swap(n, m);
    vector<vector<int>> adj(n);
    auto parse_edge = [&] (const string& s) -> pii {
        int a = 0, b = 0;
        bool done = false;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '<' || s[i] == '=') done = 1;
            else {
                if (!done) a = a * 10 + s[i] - '0';
                else b = b * 10 + s[i] - '0';
            }
        }
        return {a, b};
    };
    for (int i = 0; i < V; ++i) {
        string s;
        cin >> s;
        auto [a, b] = parse_edge(s);
        --a, --b;
        adj[a].push_back(b);
        if (find(all(s), '<') == s.end()) {
            adj[b].push_back(a);
        }
    }
    vector<vector<int>> comps;
    scc(adj, [&] (const vi& V){comps.push_back(V);});
    vector<vector<int>> dag(ncomps), rev_dag(ncomps);
    for (int i = 0; i < comps.size(); ++i) {
        map<int, bool> done;
        for (auto v: comps[i])
        for (auto u: adj[v]) {
            if (comp[u] == i) continue;
            if (!done[comp[u]]) {
                done[comp[u]] = 1;
                dag[i].push_back(comp[u]);
                rev_dag[comp[u]].push_back(i);
            }
        }
    }
    vector<bool> vis(ncomps);
    vector<int> topo;
    auto dfs = [&] (auto&& self, const vector<vi>& dag_adj, int v) -> void {
        vis[v] = 1;
        for (auto u: dag_adj[v]) {
            if (!vis[u]) self(self, dag_adj, u);
        }
        topo.push_back(v);
    };
    vector<int> dec(ncomps), inc(ncomps);
    for (int i = 0; i < ncomps; ++i) {
        if (!vis[i]) dfs(dfs, dag, i);
    }
    for (auto u: topo) {
        dec[u] = 1;
        for (auto v: dag[u]) {
            dec[u] = max(dec[u], 1 + dec[v]);
        }
    }
    vis.assign(ncomps, 0);
    for (int i = 0; i < ncomps; ++i) {
        if (!vis[i]) dfs(dfs, rev_dag, i);
    }
    for (auto u: topo) {
        inc[u] = 1;
        for (auto v: rev_dag[u]) {
            inc[u] = max(inc[u], 1 + inc[v]);
        }
    }
    for (int i = 0; i < n; ++i) {
        int c = comp[i];
        int v = dec[c] + inc[c];
        if (v == m + 1) {
            cout << "K" << inc[c] << END;
        } else {
            assert(v <= m);
            cout << "?\n";
        }
    }
}
int main()
{
    fastio
    int t = 1;
    // cin>> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

kovanice.cpp: In lambda function:
kovanice.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i = 0; i < s.size(); ++i) {
      |                         ~~^~~~~~~~~~
kovanice.cpp: In function 'void solve()':
kovanice.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < comps.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40