Submission #625899

#	Time	Username	Problem	Language	Result	Execution time	Memory
625899		resting	열쇠 (IOI21_keys)	C++17	0 / 100	4 ms	7380 KiB

keys

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

const int mx = 3e5 + 5;

class dsu {
public:
	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){
		//cout<<"omfg "<<x<<" "<<_par(x)<<" "<<p2[_par(x)]<<endl;
		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(mx), group(mx);//connected components, grouped nodes (cycle)

class node {
public:
	node(int id, int key) : id(id), sz(1), r(0), curpath(-1){
		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);
        }
        if (a.r == b.r)
			a.r++;
		a.curpath = -1; 
		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);
        }
    }

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

	// inline void addKey(int key){
    //     keys.insert(key);
	// 	if(paths.count(key)){
    //         good.insert(good.end(), paths[key].begin(), paths[key].end());
    //         paths.erase(key);
    //     }
    // }

    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, curpath;                // 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();
    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();
		int p = nodes[t].getPath();
		// cout<<t<<" -> "<<p<<endl;
		if(p == -1){
			//no parent
			//add to potential answers
			// cout<<"bruh"<<endl;
			pot.push_back(t);
		}
		else if(cc.par(t) == cc.par(p)){
			// cout<<"this doesnt happen!"<<endl;
			//there is a cycle
			//find cycle and merge and stuff
			int tmp = p;
			while(tmp != t && tmp != -1){
				int tmp2 = nodes[tmp].getPath();
				// cout<<"joining "<<t<<","<<tmp<<endl;
				node::join(nodes[t], nodes[tmp]);
				tmp = tmp2;
			}
			//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) mn = min(mn, nodes[x].getSize());
	for(auto &x : pot){
		// cout<<x<<" "<<nodes[x].getSize()<<endl;
		if(nodes[x].getSize() == mn){
			for(auto &u : nodes[x].getNodes()){
				// cout<<u<<endl;
				ans[u] = 1;
			}
		}
	}
    return ans;
}

Compilation message (stderr)

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

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