Submission #1313523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313523		windowwife	The Ties That Guide Us (CEOI23_incursion)	C++20	30 / 100	167 ms	11848 KiB

incursion

/*
SAMPLE GRADER for task INCURSION

USAGE:
place together with your solution and incursion.h in the same directory, then:
g++ <flags> sample_grader.cpp <solution_file>
e.g.:
g++ -std=c++17 sample_grader.cpp incursion.cpp

INPUT/OUTPUT:
The sample grader first expects on standard input the integers N and safe.
Afterwards, it expects the floor plan F as a sequence of N-1 pairs of integers
1 <= u, v <= N (u != v).

It will then call mark(F, safe) and write its return value T to standard output.
After this, it expects your starting location curr and will call
locate(F, curr, T[curr-1]); note that the sample grader will not change the
numbering of rooms and doors. It will then write to standard output a protocol
of all calls to visit by your program.

Upon termination, the sample grader writes your verdict to standard output.
*/

#include <bits/stdc++.h>
#define ll long long
using namespace std;

#ifndef rtgsp
#include "incursion.h"
#endif // rtgsp

#ifdef rtgsp
namespace sample_grader {

constexpr int tieLimit = 1000000000;
int N;
int dest;
int curr;
vector<int> T;
vector<pair<int, int>> F;
enum { MARK, LOCATE } phase;

[[noreturn]] void die(const char *const s) {
    cout << s << endl;
    exit(0);
}

void print_vector(vector<int> v)
{
    cout << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        cout <<  v[i];
        if (i + 1 != v.size()) cout << ", ";
    }
    cout << "}";
}

void print_vector(vector<pair<int, int>> v)
{
    cout << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        cout << "{" << v[i].first << ", " << v[i].second << "}";
        if (i + 1 != v.size()) cout << ", ";
    }
    cout << "}";
}

} // namespace sample_grader

int visit(int v) {
    using namespace sample_grader;
    function<void()> die_invalid_call_to_visit = [&]() {
        cout << "visit(" << v << ")" << endl;
        die("Invalid call to visit");
    };
    if (phase == MARK || v < 1 || v > N) die_invalid_call_to_visit();

    bool adjacent = false;
    for (auto e : F) {
        if (e == make_pair(v, curr) or e == make_pair(curr, v)) {
            adjacent = true;
        }
    }
    if (not adjacent) die_invalid_call_to_visit();

    curr = v;
    cout << "visit(" << v << ") returned " << T[v - 1] << endl;
    return T[v - 1];
}
#endif // rtgsp

const int maxn = 5e4 + 2;
vector<int> child[maxn], adj[maxn];
int n, par[maxn], sz[maxn], d[maxn];
void dfs (int u, int p)
{
    sz[u] = 1;
    for (int v : adj[u])
    {
        if (v == p)
        {
            par[u] = v;
            continue;
        }
        d[v] = d[u] + 1;
        dfs(v, u);
        sz[u] += sz[v];
        child[u].push_back(v);
    }
}
vector<int> ties;
vector<int> mark (vector<pair<int, int>> E, int safe)
{
    n = E.size() + 1;
    for (int i = 1; i <= n; i++)
    {
        adj[i].clear();
        child[i].clear();
        par[i] = d[i] = sz[i] = 0;
    }
    ties.resize(n, 0);
    for (pair<int, int> p : E)
    {
        adj[p.first].push_back(p.second);
        adj[p.second].push_back(p.first);
    }
    dfs(safe, 0);
    int c1 = -1, c2 = -1;
    for (int u = 1; u <= n; u++)
    {
        bool check = true;
        for (int v : child[u])
        {
            if (sz[v] > n/2)
            {
                check = false;
                break;
            }
        }
        if (n - sz[u] > n/2) check = false;
        if (check)
        {
            if (c1 == -1) c1 = u;
            else c2 = u;
        }
    }
    int r = -1;
    if (c2 == -1 || d[c1] < d[c2]) r = c1;
    else r = c2;
    while (r != safe)
    {
        ties[r - 1] = 1;
        r = par[r];
    }
    ties[r - 1] = 1;
    return ties;
}
bool cmp (int x, int y)
{
    return sz[x] > sz[y];
}
vector<int> path;
void locate (vector<pair<int, int>> E, int cur, int t)
{
    n = E.size() + 1;
    for (int i = 1; i <= n; i++)
    {
        adj[i].clear();
        child[i].clear();
        par[i] = d[i] = sz[i] = 0;
    }
    for (pair<int, int> p : E)
    {
        adj[p.first].push_back(p.second);
        adj[p.second].push_back(p.first);
    }
    dfs(cur, 0);
    int c1 = -1, c2 = -1;
    for (int u = 1; u <= n; u++)
    {
        bool check = true;
        for (int v : child[u])
        {
            if (sz[v] > n/2)
            {
                check = false;
                break;
            }
        }
        if (n - sz[u] > n/2) check = false;
        if (check)
        {
            if (c1 == -1) c1 = u;
            else c2 = u;
        }
    }
    int r = -1, r2 = -1;
    if (c2 == -1 || d[c1] > d[c2]) r = c1;
    else r = c2;
    r2 = r;
    while (r2 != cur)
    {
        path.push_back(r2);
        r2 = par[r2];
    }
    reverse(path.begin(), path.end());
    for (int i = 1; i <= n; i++)
    {
        child[i].clear();
        par[i] = d[i] = sz[i] = 0;
    }
    dfs(r, 0);
    if (t == 0)
    {
        for (int u : path)
        {
            t = visit(u);
            if (t == 1)
            {
                cur = u;
                break;
            }
        }
        if (cur != c1 && cur != c2) return;
    }
    for (int u = 1; u <= n; u++)
    {
        sort(child[u].begin(), child[u].end(), cmp);
    }
    while (true)
    {
        bool found = true;
        for (int v : child[cur])
        {
            t = visit(v);
            if (t == 0) visit(cur);
            else
            {
                cur = v;
                found = false;
                break;
            }
        }
        if (found) return;
    }
}

#ifdef rtgsp
int main() {
    using namespace sample_grader;
    if (!(cin >> N >> dest) or N < 2 or dest < 1 or dest > N) die("Invalid input");

    vector<int> deg(N + 1);

    for(int i = 1; i < N; ++i) {
        int u, v;
        if (!(cin >> u >> v) or min(u, v) < 1 or max(u, v) > N or u == v) {
            die("Invalid input");
        }
        F.emplace_back(u, v);
        ++deg[u]; ++deg[v];
        if(deg[u] > 3 or deg[v] > 3) die("Invalid input");
    }

    vector<bool> visited(N + 1, false);
    function<void(int)> visit = [&](int x) {
        visited[x] = true;
        for (auto [a, b] : F) {
            if (b == x) swap(a, b);
            if (a != x or visited[b]) continue;
            visit(b);
        }
    };
    visit(1);
    if (not all_of(visited.begin() + 1, visited.end(), [](bool b) { return b; })) {
        die("Invalid input");
    }

    phase = MARK;
    T = mark(F, dest);
    cout << "mark(";
    print_vector(F);
    cout << ", " << dest << ") returned ";
    print_vector(T);
    cout << endl;
    if (T.size() != static_cast<size_t>(N)) die("Invalid return value of mark");
    for (int x : T) {
        if (x < 0 or x > tieLimit) die("Invalid return value of mark");
    }

    phase = LOCATE;

    cout << "Enter curr: ";
    if (!(cin >> curr) or curr < 1 or curr > N) die("Invalid input");
    cout << "locate(";
    print_vector(F);
    cout << ", " << curr << ", " << T[curr - 1] << ")" << endl;
    locate(F, curr, T[curr - 1]);

    if (curr == dest) {
        cout << "Correct: at most " << *max_element(T.begin(), T.end()) << " tie(s) per room" << endl;
    } else {
        cout << "Not correct: current position is " << curr << endl;
    }
    return 0;
}
#endif // rtgsp

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40