제출 #1249906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1249906		tvgk	한자 끝말잇기 (JOI14_kanji)	C++20	0 / 100	549 ms	327680 KiB

Anna

#include "Annalib.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
static const long mxN = 3e2 + 7;
static const ll inf = 4e18 + 7;

static vector<int> ans[10];
static ll mn[mxN][mxN], cost[mxN][10];

void Anna(int n, int m, int a[], int b[], ll c[], int q, int s[], int t[], int k, int u[])
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            mn[i][j] = inf;
        mn[i][i] = 0;
    }

    for (int i = 0; i < m; i++)
        mn[a[i]][b[i]] = c[i];

    for (int i = 0; i < k; i++)
        mn[a[u[i]]][b[u[i]]] = inf;

    // Floyd tim min dis
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                mn[i][j] = min(mn[i][j], mn[i][k] + mn[k][j]);


    // cost[i][j] truy van s[i] -> t[i] di qua canh u[j]
    for (int i = 0; i < q; i++)
    {
        for (int j = 0; j < k; j++)
            cost[i][j] = mn[s[i]][a[u[j]]] + mn[b[u[j]]][t[i]];
        cost[i][k] = mn[s[i]][t[i]];
        ans[0].push_back(i);
    }

    vector<ii> mem;
    for (int i = 1; i <= k; i++)
    {
        ll tmp = 0;
        if (i < k)
            tmp = c[u[i]];

        vector<int> rem;
        for (int j = 0; j < i; j++)
        {
            for (int v : ans[j])
            {
                if (cost[v][j] + c[u[j]] < cost[v][i] + tmp)
                    rem.push_back(v);
                else
                    ans[i].push_back(v);
            }

            mem.push_back({ans[j].size(), rem.size()});
            ans[j] = rem;
        }
    }

    reverse(mem.begin(), mem.end());
    ll mask = 0;
    for (ii i : mem)
        mask = mask * (i.fi + 1) + i.se;

    while (mask)
    {
        Tap(mask & 1);
        mask /= 2;
    }
}

Bruno

#include "Brunolib.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
static const long mxN = 3e2 + 7;
static const ll inf = 4e18 + 7;

static ll mn[mxN][mxN], cost[mxN][mxN], c[mxN];
static vector<ii> w[mxN];
static vector<int> ans[10];
static int trace[mxN][mxN], a[mxN], b[mxN], edge[100];

void Dij(int n, int stt)
{
    for (int i = 0; i < n; i++)
    {
        mn[stt][i] = inf;
        trace[stt][i] = -1;
    }

    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push({0, stt});
    mn[stt][stt] = 0;
    while (pq.size())
    {
        ii j = pq.top();
        pq.pop();

        if (j.fi != mn[stt][j.se])
            continue;

        for (ii i : w[j.se])
        {
            if (mn[stt][i.fi] > j.fi + c[i.se])
            {
                mn[stt][i.fi] = j.fi + c[i.se];
                trace[stt][i.fi] = i.se;
                pq.push({mn[stt][i.fi], i.fi});
            }
        }
    }

//    cout << stt << '\n';
//    for (int i = 0; i < n; i++)
//        cout << trace[stt][i] << " ";
//    cout << '\n';
}

void Trace(int u, int v)
{
    vector<int> ans;
    while (v != u)
    {
        ans.push_back(trace[u][v]);
        //cout << u << " " << v << " " << trace[u][v] << '\n';
        v = a[trace[u][v]];
    }
    reverse(ans.begin(), ans.end());
    for (int i : ans)
        Answer(i);
}

void Bruno(int n, int m, int A[], int B[], long long C[], int q, int s[], int t[], int k, int u[], int l, int x[])
{
    for (int i = 0; i < m; i++)
    {
        a[i] = A[i];
        b[i] = B[i];
        c[i] = C[i];

        if (c[i] != -1)
            w[a[i]].push_back({b[i], i});
    }

    for (int i = 0; i < n; i++)
        Dij(n, i);

    // cost[i][j] truy van s[i] -> t[i] di qua canh u[j]
    for (int i = 0; i < q; i++)
    {
        for (int j = 0; j < k; j++)
            cost[i][j] = min(inf, mn[s[i]][a[u[j]]] + mn[b[u[j]]][t[i]]);
        cost[i][k] = mn[s[i]][t[i]];
        ans[0].push_back(i);
    }

    ll mask = 0;
    for (int i = 0; i < l; i++)
        mask += (1LL * x[i]) << i;

    for (int i = 1; i <= k; i++)
    {
        for (int j = 0; j < i; j++)
        {
            sort(ans[j].begin(), ans[j].end(), [&](int u, int v)
            {
                return (cost[u][j] - cost[u][i]) < (cost[v][j] - cost[v][i]);
            });

            int rem = mask % (ans[j].size() + 1);
            mask /= (ans[j].size() + 1);
            while (ans[j].size() > rem)
            {
                ans[i].push_back(ans[j].back());
                ans[j].pop_back();
            }
        }
    }

    for (int i = 0; i <= k; i++)
    {
        for (int j : ans[i])
            edge[j] = i;
    }

    for (int i = 0; i < q; i++)
    {
        // s[i], t[i];
        //cout << i << " " << edge[i] << '\n';

        if (edge[i] == k)
            Trace(s[i], t[i]);
        else
        {
            edge[i] = u[edge[i]];
            Trace(s[i], a[edge[i]]);
            Answer(edge[i]);
            Trace(b[edge[i]], t[i]);
        }
        Answer(-1);
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 8
• Subtask 4: 0 / 40
• Subtask 5: 0 / 20