Submission #459240

#	Time	Username	Problem	Language	Result	Execution time	Memory
459240		ftkbrian	Keys (IOI21_keys)	C++17	37 / 100	3191 ms	1700780 KiB

keys

#include "keys.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define f first
#define s second

int par[303030],sz[303030],chk[303030];
vector<int> V[303030],ss[303030];
vector<pii> G[303030];
int Find(int p) {
    if(par[p] == p) return p;
    return par[p] = Find(par[p]);
}
void add(int t) {
    if(chk[t]) return;
    chk[t] = 1;
    for(auto q : G[t]) {
        int a = q.f,b = q.s;
        par[a] = Find(a);
        par[b] = Find(b);
        if(sz[a] > sz[b]) swap(a,b);
        if(par[a] == par[b]) continue;
        sz[par[b]] += sz[par[a]]; sz[par[a]] = 0;
        for(auto t : V[par[a]]) {
            V[par[b]].push_back(t);
        }
        V[par[a]].clear();
        par[par[a]] = par[b];
    }
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	vector<int> ans(r.size(), -1);
	int n = r.size(),mi = n;
    for(int i = 0 ; i < c.size() ; i++) {
        if(u[i] > v[i]) swap(u[i],v[i]);
        G[c[i]].push_back({u[i],v[i]});
        if(r[u[i]] == r[v[i]] && r[u[i]] == c[i]) ss[u[i]].push_back(v[i]);
    }
    for(int i = 0 ; i < n ; i++) {
        sort(G[i].begin(),G[i].end());
        G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
    }
    for(int i = 0 ; i < n ; i++) {
        if(ans[i] != -1) continue;
        for(int q = 0 ; q < n ; q++) {
            par[q] = q,sz[q] = 1;
            V[q].clear(); V[q].push_back(r[q]);
            chk[q] = 0;
        }
        while(1) {
            int a = Find(i);
            if(V[a].empty()) break;
            int t = V[a].back(); V[a].pop_back();
            add(t);
        }
        par[i] = Find(i);
        ans[i] = sz[par[i]];
        for(auto q : ss[i]) ans[q] = ans[i];
    }

    for(int i = 0 ; i < n ; i++) {
        mi = min(mi,ans[i]);
    }
    for(int i = 0 ; i < n ; i++) {
        if(mi == ans[i]) ans[i] = 1;
        else ans[i] = 0;
    }
	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:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0 ; i < c.size() ; i++) {
      |                     ~~^~~~~~~~~~

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