Submission #470908

#	Time	Username	Problem	Language	Result	Execution time	Memory
470908		Tentacleslave	Keys (IOI21_keys)	C++17	9 / 100	375 ms	50740 KiB

keys

#include <cstdio>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int n = 0, m = 0;
vector<int> assigned_key, mutex, depth;
vector<pair<int, int>> onion;
vector<vector<pair<int, int>>> edge;
deque<int> hamburger;

int get_root(int x) {
    if(onion[x].first == x) return onion[x].first;
    onion[x].first = get_root(onion[x].first);
    return onion[x].first;
}

void big_onion(int x, int y) {
    int root = get_root(x), beet = get_root(y);
    if(root == beet) return;
    if(onion[root].second < onion[beet].second)
        onion[root].first = beet;
    else if(onion[root].second > onion[beet].second)
        onion[beet].first = root;
    else {
        onion[root].first = beet;
        onion[beet].second++;
    }
}

void dfs_init() {
    hamburger.clear();
    for(auto& i : mutex) i = 0;
    for(auto& j : depth) j = 0;
}

void dfs(int x) {
    if(mutex[x] == 1) return;
    mutex[x] = 1;
  	for(auto i : edge[x]) {
        if(assigned_key[x] == i.second || get_root(x) == get_root(i.first))
            dfs(i.first);
    }
    hamburger.push_back(x);
}

void reverse_dfs(int x, int id) {
    if(mutex[x] == 2) return;
    mutex[x] = 2;
    depth[x] = id;
  	for(auto i : edge[x]) {
        if(assigned_key[i.first] == i.second || get_root(x) == get_root(i.first))
            reverse_dfs(i.first, id);
    }
}

void dfs_final(int x, vector<int>& log) {
    if(mutex[x]) return;
  	
    mutex[x] = 1;
    
  	for(auto i : edge[x]) {
        if(assigned_key[x] == i.second || get_root(x) == get_root(i.first)) {
            if(get_root(x) != get_root(i.first))
              	log[get_root(x)] = true;
            dfs_final(i.first, log);
        }
    }
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = r.size(), m = u.size();
    onion.resize(n, {0, 0});
    edge.resize(n, {});
  	mutex.resize(n, 0);
  	depth.resize(n, 0);
    
    assigned_key = r;
  	
  	for(int i = 0; i < n; i++) onion[i].first = i;
    
    for(int i = 0; i < m; i++) {
        edge[u[i]].push_back({v[i], c[i]});
        edge[v[i]].push_back({u[i], c[i]});
    }
  	
  	int prev = n, curr = 0;
    
  	while(prev != curr) {
        prev = curr;
        curr = 0;
        int increment = 0;
  	    dfs_init();
        vector<vector<int>> counting;
        counting.resize(n, {});
        
        for(int i = 0; i < n; i++) dfs(i);
        while(hamburger.size()) {
          	int top = hamburger.back();
            reverse_dfs(top, increment);
            hamburger.pop_back();
            increment++;
        }
        for(int i = 0; i < n; i++)
            counting[depth[i]].push_back(i);
        for(int i = 0; i < n; i++) {
            if(counting[i].empty()) continue;
            curr++;
            for(int j = 1; j < counting[i].size(); j++)
                big_onion(counting[i][j - 1], counting[i][j]);
        }
    }
  	
final_tentacular_boss:
  	
    vector<int> ans;
    vector<vector<int>> counting;
    vector<int> log;
    ans.resize(n, 0);
    log.resize(n, 0);
    counting.resize(n, {});
  	
  	dfs_init();
  	
  	for(int i = 0; i < n; i++) dfs_final(i, log);
  	
  	for(int i = 0; i < n; i++) {
      	if(log[get_root(i)]) continue;
      	counting[get_root(i)].push_back(i);
    }
    
    int min_size = 1e9;
    
    for(int i = 0; i < n; i++) {
        if(counting[i].empty()) continue;
        if(min_size > counting[i].size())
       		min_size = counting[i].size();
    }
  	for(int i = 0; i < n; i++) {
        if(counting[i].empty()) continue;
        if(min_size == counting[i].size())
            for(auto j : counting[i])
           	    ans[j] = 1;
    }
  	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:111:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for(int j = 1; j < counting[i].size(); j++)
      |                            ~~^~~~~~~~~~~~~~~~~~~~
keys.cpp:138:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         if(min_size > counting[i].size())
      |            ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
keys.cpp:143:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         if(min_size == counting[i].size())
      |            ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
keys.cpp:116:1: warning: label 'final_tentacular_boss' defined but not used [-Wunused-label]
  116 | final_tentacular_boss:
      | ^~~~~~~~~~~~~~~~~~~~~

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