Submission #470890

#	Time	Username	Problem	Language	Result	Execution time	Memory
470890		Tentacleslave	Keys (IOI21_keys)	C++17	0 / 100	1 ms	280 KiB

keys

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int increment = 0, n = 0, m = 0;
vector<int> assigned_key, mutex, depth, vital;
vector<pair<int, int>> vertex_onion, key_onion;
vector<vector<pair<int, int>>> edge;
multimap<int, int> acyclic;

int get_root(int x, vector<pair<int, int>>& onion) {
    if(onion[x].first == x) return onion[x].first;
    onion[x].first = get_root(onion[x].first, onion);
    return onion[x].first;
}

void big_onion(int x, int y, vector<pair<int, int>>& onion) {
    int root = get_root(x, onion), beet = get_root(y, onion);
    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() {
    increment = 0;
    for(auto& i : mutex) i = 0;
    for(auto& i : depth) i = 0;
}

int dfs(int x) {
    if(mutex[x] == 1) return depth[x];
    if(mutex[x] == 2) return -1;
  	
    mutex[x] = 1;
    int min = increment;
    depth[x] = min;
    
    increment++;
  	
  	for(auto i : edge[x]) {
        if(get_root(assigned_key[x], key_onion) == get_root(i.second, key_onion)) {
            int val = dfs(i.first);
            if(min > val && val != -1)
                min = val;
        }
    }
    
    depth[x] = min;
  	mutex[x] = 2;
    return min;
}

void dfs_final(int x, vector<int>& log) {
    if(mutex[x]) return;
  	
    mutex[x] = 1;
    
    increment++;
  	
  	for(auto i : edge[x]) {
        if(get_root(assigned_key[x], key_onion) == get_root(i.second, key_onion)) {
            if(get_root(x, vertex_onion) != get_root(i.first, vertex_onion))
              	log[get_root(x, vertex_onion)] = 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();
    vertex_onion.resize(n, {0, 0});
    key_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++)
      	key_onion[i].first = vertex_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]});
    }
    
  	for(int step = 0; step < 20; step++) {
  	    dfs_init();
        vector<vector<int>> counting;
        counting.resize(n, {});
        
        for(int i = 0; i < n; i++) dfs(i);
        for(int i = 0; i < n; i++)
            counting[depth[i]].push_back(i);
        for(int i = 0; i < n; i++) {
            if(counting[i].size() < 2) continue;
            for(int j = 1; j < counting[i].size(); j++) {
                big_onion(counting[i][j - 1], counting[i][j], vertex_onion);
                big_onion(assigned_key[counting[i][j - 1]], assigned_key[counting[i][j]], key_onion);
            }
        }
    }
  	
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, vertex_onion)]) continue;
      	counting[get_root(i, vertex_onion)].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:106:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             for(int j = 1; j < counting[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~
keys.cpp:135:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         if(min_size > counting[i].size())
      |            ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
keys.cpp:140:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         if(min_size == counting[i].size())
      |            ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
keys.cpp:113:1: warning: label 'final_tentacular_boss' defined but not used [-Wunused-label]
  113 | final_tentacular_boss:
      | ^~~~~~~~~~~~~~~~~~~~~

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