Submission #708186

#	Time	Username	Problem	Language	Result	Execution time	Memory
708186		Cyanmond	Simurgh (IOI17_simurgh)	C++17	51 / 100	384 ms	4056 KiB

simurgh

#include "simurgh.h"
/*
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>

using namespace std;

static int MAXQ = 30000;

static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;

static void wrong_answer() {
    printf("NO\n");
    exit(0);
}

static bool is_valid(const vector<int> &r) {
    if (int(r.size()) != n - 1) return false;

    for (int i = 0; i < n - 1; i++)
        if (r[i] < 0 || r[i] >= m) return false;

    return true;
}

static int _count_common_roads_internal(const vector<int> &r) {
    if (!is_valid(r)) wrong_answer();

    int common = 0;
    for (int i = 0; i < n - 1; i++) {
        bool is_common = goal[r[i]];
        if (is_common) common++;
    }

    return common;
}

int count_common_roads(const vector<int> &r) {
    q++;
    if (q > MAXQ) wrong_answer();

    return _count_common_roads_internal(r);
}
*/
#include <bits/stdc++.h>

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    const int m = (int)u.size();
    std::vector<int> edgeType(m, -1);
    for (int i = 0; i < n; ++i) {
        std::vector<int> e1, e2;
        for (int j = 0; j < m; ++j) {
            if (u[j] == i or v[j] == i) {
                e1.push_back(j);
            } else {
                e2.push_back(j);
            }
        }
        std::vector<std::vector<std::pair<int, int>>> graph(n);
        for (const int x : e2) {
            graph[u[x]].push_back({v[x], x});
            graph[v[x]].push_back({u[x], x});
        }
        std::vector<bool> isSeen(n);
        int cnt = 0;
        std::vector<int> id(n), treeEdges;
        for (int f = 0; f < n; ++f) {
            if (isSeen[f]) continue;
            if (f == i) continue;
            std::queue<int> que;
            que.push(f);
            isSeen[f] = true;
            while (not que.empty()) {
                const int x = que.front();
                que.pop();
                id[x] = cnt;
                for (const auto &[t, y] : graph[x]) {
                    if (not isSeen[t]) {
                        treeEdges.push_back(y);
                        que.push(t);
                        isSeen[t] = true;
                    }
                }
            }
            ++cnt;
        }
        const int R = cnt;
        std::vector<std::vector<int>> eDivided(R);
        for (const int x : e1) {
            if (u[x] == i) {
                eDivided[id[v[x]]].push_back(x);
            } else {
                eDivided[id[u[x]]].push_back(x);
            }
        }

        for (int f = 0; f < R; ++f) {
            auto &vec = eDivided[f];
            const int T = (int)vec.size();
            for (int j = 0; j < R; ++j) {
                if (j != f) {
                    treeEdges.push_back(eDivided[j][0]);
                }
            }
            std::vector<int> vals(T);
            for (int j = 0; j < T; ++j) {
                if (edgeType[vec[j]] != -1) {
                    std::swap(vec[j], vec[0]);
                }
            }
            if (edgeType[vec[0]] == -1) {
                for (int j = 0; j < T; ++j) {
                    treeEdges.push_back(vec[j]);
                    vals[j] = count_common_roads(treeEdges);
                    treeEdges.pop_back();
                }
                const int ma = *std::max_element(vals.begin(), vals.end());
                for (int j = 0; j < T; ++j) {
                    if (vals[j] == ma) {
                        edgeType[vec[j]] = 1;
                    } else {
                        edgeType[vec[j]] = 0;
                    }
                }
            } else {
                treeEdges.push_back(vec[0]);
                int ma = count_common_roads(treeEdges);
                treeEdges.pop_back();
                if (edgeType[vec[0]] == 0) {
                    ++ma;
                }
                for (int j = 0; j < T; ++j) {
                    if (edgeType[vec[j]] != -1) {
                        continue;
                    }
                    treeEdges.push_back(vec[j]);
                    const int val = count_common_roads(treeEdges);
                    if (ma == val) {
                        edgeType[vec[j]] = 1;
                    } else {
                        edgeType[vec[j]] = 0;
                    }
                    treeEdges.pop_back();
                }
            }
            for (int j = 0; j < R - 1; ++j) {
                treeEdges.pop_back();
            }
        }
    }
    std::vector<int> ret;
    for (int i = 0; i < m; ++i) {
        if (edgeType[i] == 1) {
            ret.push_back(i);
        }
    }
    return ret;
}
/*
int main() {
    assert(2 == scanf("%d %d", &n, &m));

    u.resize(m);
    v.resize(m);

    for (int i = 0; i < m; i++) assert(2 == scanf("%d %d", &u[i], &v[i]));

    goal.resize(m, false);

    for (int i = 0; i < n - 1; i++) {
        int id;
        assert(1 == scanf("%d", &id));
        goal[id] = true;
    }

    vector<int> res = find_roads(n, u, v);

    if (_count_common_roads_internal(res) != n - 1) wrong_answer();

    printf("YES\n");

    return 0;
}
*/

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30