Submission #629777

#	Time	Username	Problem	Language	Result	Execution time	Memory
629777		Cross_Ratio	Keys (IOI21_keys)	C++17	37 / 100	3050 ms	89232 KiB

keys

#include <bits/stdc++.h>
using namespace std;
int R[300005];
typedef pair<int,int> P;
vector<vector<P>> adj;
int res[300005];
int N;
vector<int> find_reachable(vector<int> _R, vector<int> _U, vector<int> _V, vector<int> _C) {
	N = _R.size();
	int i, j;
	for(i=0;i<N;i++) R[i] = _R[i];
	adj.resize(N);
	for(i=0;i<_U.size();i++) {
        adj[_U[i]].push_back(P(_V[i],_C[i]));
        adj[_V[i]].push_back(P(_U[i],_C[i]));
	}
	for(i=0;i<N;i++) {
        int org = R[i];
        vector<queue<int>> Q;
        Q.resize(N);
        vector<bool> vis;
        vector<int> cord;
        cord.resize(N);
        for(j=0;j<N;j++) cord[j] = j;
        vis.resize(N);
        res[i]++;
        vis[i] = true;
        for(P k : adj[i]) {
            Q[cord[k.second]].push(k.first);
        }
        while(!Q[org].empty()) {
            int c = Q[org].front();
            //cout << c << ' ';
            Q[org].pop();
            if(vis[c]) continue;
            vis[c] = true;
            res[i]++;
            for(P k : adj[c]) {
                Q[cord[k.second]].push(k.first);
            }
            if(cord[R[c]]!=org) {
                cord[R[c]] = org;
                while(!Q[R[c]].empty()) {
                    int n = Q[R[c]].front();
                    Q[R[c]].pop();
                    Q[org].push(n);
                }
            }
        }
        //cout << '\n' << res[i] << '\n';
	}
	int mi = 1e9;
	for(i=0;i<N;i++) mi = min(mi, res[i]);
	vector<int> ans;
	ans.resize(N);
	for(i=0;i<N;i++) {
        if(res[i]==mi) ans[i] = 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:13:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(i=0;i<_U.size();i++) {
      |          ~^~~~~~~~~~

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