Submission #627007

#	Time	Username	Problem	Language	Result	Execution time	Memory
627007		resting	Keys (IOI21_keys)	C++17	100 / 100	1252 ms	160492 KiB

keys

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

const int mx = 3e5 + 5;

class dsu {
public:
	dsu(){}
	dsu(int n) {
		p.resize(n, -1);
		p2.resize(n);
		for(int i = 0; i < n; i++)
			p2[i] = i;
		r.resize(n, 0);
	}

	int par(int x){
		return p2[_par(x)];
	}

	void join(int a, int b){
		a = _par(a); b = _par(b);
		if (a == b) return;
		p2[b] = p2[a];
		if (r[a] < r[b]) swap(a, b);
		if (r[a] == r[b]) r[a]++;
		p[b] = a;
	}

private:
	int _par(int x){
		return p[x] == -1 ? x : p[x] = _par(p[x]);
	}
	vector<int> p, r, p2;
} cc, group;//connected components, grouped nodes (cycle)

class node {
public:
	node(int id, int key) : id(id), sz(1), r(0){
		nodes.push_back(id);
		keys.insert(key);
    }
    node() : node(-1, -1){};
    static void join(node &a, node &b) {
		if (a.r < b.r){
			swap(a, b);
			swap(a.id, b.id);
			swap(a.good, b.good);
        }
        if (a.r == b.r)
			a.r++;
		a.sz += b.sz;
        group.join(a.id, b.id);
        a.keys.insert(b.keys.begin(), b.keys.end());
		a.nodes.insert(a.nodes.end(), b.nodes.begin(), b.nodes.end());
		for (auto &x : b.paths){
            if (a.keys.count(x.first)){
                a.good.insert(a.good.end(), x.second.begin(), x.second.end());
            }
            else{
                a.paths[x.first].insert(a.paths[x.first].end(), x.second.begin(), x.second.end());
            }
        }
		for (auto &x : b.keys){
			if (!a.paths.count(x))
				continue;
			a.good.insert(a.good.end(), a.paths[x].begin(), a.paths[x].end());
			a.paths.erase(x);
        }
		a.good.insert(a.good.end(), b.good.begin(), b.good.end());
    }

    inline int getPath() {
        while (good.size() && group.par(good.back()) == group.par(id))
            good.pop_back();
        if (!good.size()) return -1;
		return group.par(good.back());
    }

	inline int getID(){
		return id;
	}

    inline void addPath(int to, int key){
		if(keys.count(key)) {
            good.push_back(to);
        }
		else{
            paths[key].push_back(to);
        }
    }

	inline int getSize(){
		return sz;
	}

	inline vector<int>& getNodes(){
		return nodes;
	}

private:
	int sz, id, r;       // rank ensures that at most logn times :DD
    map<int, vector<int>> paths;  // color, destination
    vector<int> good;             // paths that you have key to :D
	vector<int> nodes;            // everything in this node so we can output
    set<int> keys;                //list of keys
};

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    const int n = r.size();
    const int m = u.size();
	cc = dsu(n);
	group = dsu(n);
    std::vector<int> ans(n, 0);
    vector<node> nodes(n);
    vector<int> q;
	vector<int> pot;
    for (int i = 0; i < n; i++){
        nodes[i] = node(i, r[i]);
        q.push_back(i);
    }
    for (int i = 0; i < m; i++){
        nodes[u[i]].addPath(v[i], c[i]);
        nodes[v[i]].addPath(u[i], c[i]);
    }
	while(!q.empty()){
		int t = q.back();
		q.pop_back();
		//assert(nodes[t].getID() == t);
		//assert(group.par(t) == t);
		int p = nodes[t].getPath();
		if(p == -1){
			//no parent
			//add to potential answers
			pot.push_back(t);
		}
		else if(cc.par(t) == cc.par(p)){
			//there is a cycle
			//merge and stuff
			//assert(find(q.begin(), q.end(), p) == q.end());
			//int k = nodes[t].getID();
			node::join(nodes[t], nodes[p]);
			//assert(nodes[t].getID() == k);
			//no more par so put it back in the queue
			q.push_back(t);
		}
		else {
			cc.join(t, p);
		}
    }
	int mn = n;
	for(auto &x : pot) {
		//assert(group.par(x) == x);
		mn = min(mn, nodes[x].getSize());
	}
	for(auto &x : pot){
		if(nodes[x].getSize() == mn){
			for(auto &u : nodes[x].getNodes()){
				ans[u] = 1;
			}
		}
	}
    return ans;
}

Compilation message (stderr)

keys.cpp: In constructor 'node::node(int, int)':
keys.cpp:102:10: warning: 'node::id' will be initialized after [-Wreorder]
  102 |  int sz, id, r;       // rank ensures that at most logn times :DD
      |          ^~
keys.cpp:102:6: warning:   'int node::sz' [-Wreorder]
  102 |  int sz, id, r;       // rank ensures that at most logn times :DD
      |      ^~
keys.cpp:39:2: warning:   when initialized here [-Wreorder]
   39 |  node(int id, int key) : id(id), sz(1), r(0){
      |  ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33