Submission #1139874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139874		elsantodel90	Werewolf (IOI18_werewolf)	C++20	15 / 100	950 ms	82948 KiB

werewolf

#include "werewolf.h"
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)

#define SIZE(c) int((c).size())
#define ALL(c) begin(c), end(c)
#define DBG(x) cerr << #x << " = " << (x) << endl

template <typename T>
ostream & operator<<(ostream &os, const vector<T> &v)
{
    os << "[";
    forn(i,SIZE(v))
    {
        if (i > 0)
            os << ",";
        os << v[i];
    }
    os << "]";
    return os;
}

const int MAXN = 3500;

// minMax[0] es la normal
// minMax[1] es la opuesta (o sea que da el maxmin)

int minMax[2][MAXN][MAXN];
vector<int> neighbors[MAXN];

struct Item
{
    int node;
    int dist;
    bool operator <(const Item &o) const
    {
        return dist > o.dist;
    }
};

const int INF = 1000000000;

void dijkstra(int N, int start, int inverted)
{
    int *dist = minMax[inverted][start];
    // Siempre calcula el minMax
    // Si esta inverted, usa "-nodeId"
    forn(i,N)
        dist[i] = INF;
    priority_queue<Item> pq;
    #define COST(x) (inverted ? (-x) : x)
    #define PUT(node, d) do {dist[node] = d; pq.push({node, d});} while (false)
    PUT(start, COST(start));
    while (!pq.empty())
    {
        Item item = pq.top();
        pq.pop();
        if (dist[item.node] != item.dist)
            continue;
        for (int y : neighbors[item.node])
        {
            int newDist = max(item.dist, COST(y));
            if (newDist < dist[y])
                PUT(y, newDist);
        }
    }
    
    if (inverted)
    forn(i,N)
        dist[i] = -dist[i];
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    const int M = SIZE(X);
    forn(i, M)
    {
        #define ADD_NEIGHBOR(a,b) do {neighbors[a].push_back(b); } while (false)
        ADD_NEIGHBOR(X[i],Y[i]);
        ADD_NEIGHBOR(Y[i],X[i]);
    }
    forn(inverted, 2)
    forn(start, N)
        dijkstra(N, start, inverted);
    const int Q = SIZE(S);
    vector<int> ret(Q, 0);
    forn(i,Q)
    forn(mid, N)
    if (minMax[1][S[i]][mid] >= L[i] &&
        minMax[0][mid][E[i]] <= R[i])
    {
        ret[i] = 1;
        break;
    }
    return ret;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51