oj.uz

Submission #893237

# Submission time Handle Problem Language Result Execution time Memory
893237 2023-12-26T18:34:08 Z vjudge1 Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 600 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct UF {
    vi e;
    UF(int N) : e(N, -1) {}
    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }
    int join(int u, int v) {
        u = repr(u); v = repr(v);
        if(u == v) return 0;
        if(e[u] > e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        return 1;
    }
    bool same(int u, int v) { return repr(u) == repr(v); }
    void clear() { for(auto &it : e) it = -1; }
};

vi find_roads(int n, vi u, vi v) {
    int m = u.size();
    UF sol(n);
    vector<vi> L(n);
    for(int i = 0; i < m; ++i) {
        L[u[i]].push_back(v[i]);
        L[v[i]].push_back(u[i]);
    }
    vi Re;
    for(int i = 0; i < n; ++i) {
        sol.clear();
        vector<int> Q;
        for(int j = 0; j < m; ++j) {
            if(u[j] != i && v[j] != i) {
                if(sol.join(u[j], v[j])) {
                    Q.push_back(j);
                }
            }
        }
     //   vector<int> Cul;
     //   for(int j = 0; j < m; ++j) {
     //       if(u[j] == i || v[j] == i) {
     //           int x = u[j];
     //           if(x == i) x = v[j];
     //           Cul.push_back(sol.repr(x));
     //       }
     //   }
     //   sort(Cul.begin(), Cul.end());
     //   Cul.resize(unique(Cul.begin(), Cul.end()) - Cul.begin());
     //   auto id = [&](int v) {
     //       return lower_bound(Cul.begin(), Cul.end(), v) - Cul.begin();
     //   };
        map<int, vector<int> > M;
        for(int j = 0; j < m; ++j) {
            if(u[j] == i || v[j] == i) {
                int x = u[j];
                if(x == i) x = v[j];
                M[sol.repr(x)].push_back(j);
            }
        }
        for(auto [cul, vec] : M) {
            vi QQ = Q;
            for(auto [altcul, altvec] : M)
                if(altcul != cul)
                    QQ.push_back(altvec[0]);
            int rem = 0, muchie = 0;
            for(auto it : vec) {
                QQ.push_back(it);
                int v = count_common_roads(QQ);
                QQ.pop_back();
                if(v > rem) {
                    rem = v;
                    muchie = it;
                }
            }
            Re.push_back(muchie);
        }
    }
    sort(Re.begin(), Re.end());
    Re.resize(unique(Re.begin(), Re.end()) - Re.begin());
    assert(Re.size() == (n - 1));
    return Re;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:87:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |     assert(Re.size() == (n - 1));
      |            ~~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Runtime error 1 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Runtime error 1 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Runtime error 1 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Runtime error 1 ms 348 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Runtime error 1 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -