제출 #470905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470905		Tentacleslave	열쇠 (IOI21_keys)	C++17	9 / 100	3083 ms	53164 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>> vertex_onion, key_onion;
vector<vector<pair<int, int>>> edge;
deque<int> hamburger;

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() {
    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(get_root(assigned_key[x], key_onion) == get_root(i.second, key_onion))
            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(get_root(assigned_key[i.first], key_onion) == get_root(i.second, key_onion))
            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(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++)
      	vertex_onion[i].first = key_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 < 30; step++) {
        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].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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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