Submission #1283355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283355		feining_for_gm	Meetings (JOI19_meetings)	C++20	29 / 100	392 ms	1012 KiB

meetings

// meetings.cpp
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

// ---------- Utilities ----------
static inline long long keyEdge(int u, int v) {
    if (u > v) swap(u, v);
    return ( (long long)u << 21 ) ^ (long long)v; // N <= 2000 fits well
}

struct Reconstructor {
    int N;
    vector<vector<int>> adj; // for optional internal checks (not needed by grader)
    unordered_set<long long> edge_set; // to avoid duplicate Bridge calls

    Reconstructor(int n): N(n) {
        adj.assign(N, {});
        edge_set.reserve(2*N);
    }

    // Safely add one real edge (u,v) once.
    void add_edge(int u, int v) {
        if (u > v) swap(u, v);
        long long k = keyEdge(u, v);
        if (edge_set.insert(k).second) {
            // Record edge for sanity (optional)
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }

    // Projection of x onto path (A,B). Avoids duplicate-node queries.
    int project(int A, int B, int x) {
        if (x == A) return A;
        if (x == B) return B;
        return Query(A, B, x);
    }

    // Find diameter endpoints of set S (one pass, ~|S|-2 queries).
    pair<int,int> find_diameter(const vector<int>& S) {
        int a = S[0];
        int b = S[1 % (int)S.size()];
        for (int i = 0; i < (int)S.size(); ++i) {
            int x = S[i];
            if (x == a || x == b) continue;
            int p = project(a, b, x);
            if (p == a) a = x;
            else if (p == b) b = x;
            // else x is inside current path; ignore
        }
        return {a, b};
    }

    // Comparator to order nodes u,v that we know lie on path A-B:
    // u comes before v from A towards B iff Query(A,u,v) == u.
    struct PathLess {
        int A;
        PathLess(int A): A(A) {}
        bool operator()(int u, int v) const {
            if (u == v) return false;
            if (u == A) return true;
            if (v == A) return false;
            int m = Query(A, u, v);
            return m == u; // u is between A and v => u is closer to A than v
        }
    };

    void build_on_set(const vector<int>& S) {
        if ((int)S.size() <= 1) return;

        // 1) Find diameter endpoints (A,B)
        auto pr = find_diameter(S);
        int A = pr.first, B = pr.second;

        // 2) Project everything onto A-B, split into on-path and buckets
        vector<int> onpath;
        onpath.reserve(S.size());
        unordered_map<int, vector<int>> bucket; // projection point -> nodes hanging there
        bucket.reserve(S.size()*2);

        for (int x : S) {
            int p;
            if (x == A || x == B) {
                p = x; // avoid duplicate-node query
            } else {
                p = project(A, B, x);
            }
            if (p == x) {
                onpath.push_back(x);
            } else {
                bucket[p].push_back(x);
            }
        }

        // 3) Sort path nodes from A to B using median comparator
        // (A will naturally be first due to the comparator handling)
        sort(onpath.begin(), onpath.end(), PathLess(A));

        // 4) Add edges along this path (consecutive nodes are adjacent in the real tree)
        for (int i = 0; i + 1 < (int)onpath.size(); ++i) {
            add_edge(onpath[i], onpath[i+1]);
        }

        // 5) Recurse on each hanging component {t} ∪ bucket[t]
        for (int t : onpath) {
            auto it = bucket.find(t);
            if (it == bucket.end() || it->second.empty()) continue;
            vector<int> sub;
            sub.reserve(it->second.size() + 1);
            sub.push_back(t);
            for (int v : it->second) sub.push_back(v);
            build_on_set(sub);
        }
    }

    void run() {
        // Start with the full set of nodes
        vector<int> all(N);
        iota(all.begin(), all.end(), 0);
        build_on_set(all);

        // At this point we should have exactly N-1 distinct edges.
        // Report them via Bridge(u,v).
        // (The grader requires exactly N-1 calls, all correct and unique.)
        // For determinism, iterate through adjacency or through the set.
        // We'll iterate through the set we maintained.
        vector<pair<int,int>> edges;
        edges.reserve(N-1);
        edges.clear();
        for (long long k : edge_set) {
            int u = (int)(k >> 21);
            int v = (int)(k & ((1<<21)-1));
            edges.emplace_back(u, v);
        }
        // Sanity: ensure exactly N-1
        // (If not, still output what we have; the grader will judge.)
        // But the algorithm constructs exactly N-1 unique edges.
        for (auto &e : edges) {
            Bridge(e.first, e.second);
        }
    }
};

void Solve(int N) {
    Reconstructor rec(N);
    rec.run();
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71