Submission #470695

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

keys

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

using namespace std;

int increment, total_size;
vector<int> scc_value;
vector<int> mutex;

int dfs(int v, const vector<int>& vertex, const vector<vector<pair<int, int>>>& edge_table) {
    if(mutex[v] == 1)
        return scc_value[v];
    
    if(mutex[v] == 2)
        return -1;

    mutex[v] = 1;
    
    int min = increment;
    
    scc_value[v] = min;
    
    increment++;
    
    for(auto i : edge_table[v]) {
        if(vertex[v] != i.second) continue;
        int fetch = dfs(i.first, vertex, edge_table);
        if(min > fetch && fetch != -1)
            min = fetch;
    }
    
    scc_value[v] = min;
    
    mutex[v] = 2;
    
    return min;
}

vector<int> find_components(const vector<int>& vertex, const vector<vector<pair<int, int>>>& edge_table) {
    
    increment = 0;
    scc_value.resize(vertex.size());
    mutex.resize(vertex.size());
  
    fill (scc_value.begin(), scc_value.end(), 0);
    fill (mutex.begin(), mutex.end(), 0);
    for(vector<int>::const_iterator i = vertex.begin(); i != vertex.end(); i++)
        dfs(i - vertex.begin(), vertex, edge_table);
    
    return scc_value;
}

// vertex weighted by (key, list of subvertex), edge weighted by (connector's key id)
vector<int> find_reachable_internal(vector<pair<int, vector<int>>> vertex, vector<vector<pair<int, int>>> edge_table) {
    vector<int> simple_vertex;
    for(auto i : vertex)
        simple_vertex.push_back(i.first);
  	vector<int> scc_table = find_components(simple_vertex, edge_table);

	// To-do: construct new graph consists of SCC
    // Required: mapping vertex to SCC number ... vertex (--- scc_table --->) (--- scc_map --->) new_vertex
    // Do not fetch: for all SCC, size = 1
    
    vector<int> reverse_map = scc_table;
    std::sort(reverse_map.begin(), reverse_map.end());
    reverse_map.erase(unique(reverse_map.begin(), reverse_map.end()), reverse_map.end());
    
    if(reverse_map.size() == vertex.size()) {
        int min_size = 1e9;
        for(auto i : vertex) {
            bool res = false;
            for(auto j : edge_table[i.first]) {
                if(i.first == j.second)
                    res = true;
            }
            if(res) i.second.clear();
            if(min_size > i.second.size() && i.second.size() > 0)
                min_size = i.second.size();
        }
        vector<int> restored_vertex;
        restored_vertex.resize(total_size, 0);
        for(auto i : vertex) {
            for(auto j : i.second) {
                if(i.second.size() == min_size)
                    restored_vertex[j] = 0;
                else
                    restored_vertex[j] = 1;
            }
        }
        return restored_vertex;
    }
    
    // To-do: Query
    
    vector<int> scc_map;
    scc_map.resize(vertex.size(), 0);
    
    for(vector<int>::iterator i = reverse_map.begin(); i != reverse_map.end(); i++)
        scc_map[*i] = i - reverse_map.begin();
    
    vector<pair<int, vector<int>>> new_vertex;
    
    new_vertex.resize(reverse_map.size(), {0, {}});
    
    for(auto i = new_vertex.begin(); i != new_vertex.end(); i++) {
        i->first = i - new_vertex.begin();
    }
    
    for(vector<pair<int, vector<int>>>::const_iterator i = vertex.begin(); i != vertex.end(); i++) {
        int pos = i - vertex.begin();
        for(auto j : i->second)
     	    new_vertex[scc_map[scc_table[pos]]].second.push_back(j);
    }
    
    vector<vector<pair<int, int>>> new_edge_table;
    
    new_edge_table.resize(reverse_map.size(), {});
    
    for(vector<vector<pair<int, int>>>::const_iterator i = edge_table.begin(); i != edge_table.end(); i++) {
        int arg1 = scc_map[scc_table[i - edge_table.begin()]];
        for(auto j : *i) {
            int arg2 = scc_map[scc_table[j.first]];
        	int arg3 = scc_map[scc_table[j.second]];
            new_edge_table[arg1].push_back({arg2, arg3});
        }
    }
	
  	return find_reachable_internal(new_vertex, new_edge_table);
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    total_size = r.size();
    int edge_size = u.size();
    
    vector<pair<int, vector<int>>> vertex;
    vector<vector<pair<int, int>>> edge_table;
    
    for(int i = 0; i < total_size; i++) {
        vertex.push_back({r[i], {i}});
    }
    edge_table.resize(vertex.size(), {});
    
    for(auto i = u.begin(), j = v.begin(), k = c.begin(); i != u.end() && j != v.end() && k != c.end(); i++, j++, k++) {
        edge_table[*i].push_back({*j, *k});
        edge_table[*j].push_back({*i, *k});
    }
    
    return find_reachable_internal(vertex, edge_table);
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable_internal(std::vector<std::pair<int, std::vector<int> > >, std::vector<std::vector<std::pair<int, int> > >)':
keys.cpp:57:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   57 |     for(auto i : vertex)
      |     ^~~
keys.cpp:59:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   59 |    vector<int> scc_table = find_components(simple_vertex, edge_table);
      |    ^~~~~~
keys.cpp:78:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             if(min_size > i.second.size() && i.second.size() > 0)
      |                ~~~~~~~~~^~~~~~~~~~~~~~~~~
keys.cpp:85:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |                 if(i.second.size() == min_size)
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:134:9: warning: unused variable 'edge_size' [-Wunused-variable]
  134 |     int edge_size = u.size();
      |         ^~~~~~~~~

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