Submission #1370685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370685		solution6312	Theseus (CEOI25_theseus)	C++17	24 / 100	43 ms	6004 KiB

theseus

#include <iostream>
#include <vector>
#include <cassert>
#include <queue>
using namespace std;
using pii=pair<int, int>;

namespace
{
    const int MN=1e4+13;
    int N, T, d[MN];
    vector<int> G[MN];
    void bfs()
    {
        for (int i=1; i<=N; i++) d[i]=-1;
        queue<int> q;
        d[T]=0;
        q.push(T);
        while (q.size())
        {
            int u=q.front(); q.pop();
            for (int v:G[u]) if (d[v]==-1)
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
}

vector<int> paint(int n, vector<pii> E, int t)
{
    N=n; T=t;
    for (int i=1; i<=N; i++) G[i].clear();
    for (auto [U, V]:E)
    {
        G[U].push_back(V);
        G[V].push_back(U);
    }
    bfs();
    vector<int> ans;
    for (auto [U, V]:E)
    {
        if (d[U]==d[V]+1) ans.push_back((U>V));
        else
        {
            assert(d[U]+1==d[V]);
            ans.push_back((U<V));
        }
    }
    return ans;
}

int travel(int N, int U, vector<pii> G)
{
    for (auto [x, y]:G)
    {
        if (!y && U<x) return x;
        else if (y && U>x) return x;
    }
    assert(0);
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 13 / 13
• Subtask 5: 0 / 12
• Subtask 6: 0 / 50