제출 #216539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216539		emil_physmath	Simurgh (IOI17_simurgh)	C++17	70 / 100	680 ms	38496 KiB

simurgh

#include "simurgh.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define query count_common_roads
const int maxN = 500;
struct Jmp
{
    int to, ind;
    operator int&() { return to; }
    operator const int&() const { return to; }
};

int n;
int in[maxN], out[maxN];
Jmp par[maxN];
int gold[maxN * maxN];
vector<int> dfsq;
vector<Jmp> nei[maxN];
vector<int> same[maxN * maxN];
Jmp fup[maxN];

map<vector<int>, int> cache;
int Query(vector<int> q)
{
    sort(q.begin(), q.end());
    auto it = cache.find(q);
    if (it != cache.end()) return it->second;
    return cache[q] = query(q);
}
inline bool Upper(int u, int v) { return in[u] <= in[v] && out[u] >= out[v]; }
bool used[maxN];
void DFS(int v, Jmp p)
{
    // cerr << "v: " << v << '\n';
    static int time = 0;
    used[v] = true;
    in[v] = ++time;
    par[v] = p;
    fup[v] = {-1, -1};
    for (Jmp to: nei[v])
        if (!used[to])
        {
            dfsq.push_back(to.ind);
            DFS(to, {v, to.ind});
            if (p != -1)
                if (fup[v] == -1 || (fup[to] != -1 && in[fup[to]] <= in[fup[v]]))
                    fup[v] = fup[to];
        }
        else if (to != p && p != -1)
            if (fup[v] == -1 || in[to] <= in[fup[v]])
                fup[v] = to;
    out[v] = time;
}

void DFS1(int v)
{
    for (int to: same[v])
        if (gold[to] == -1)
        {
            gold[to] = gold[v];
            DFS1(to);
        }
}
int pr[maxN * maxN], sz[maxN * maxN], ok[maxN * maxN];
void MakeSet(int i) { pr[i] = i; sz[i] = 1; }
int Set(int i) { return pr[i] == i ? i : pr[i] = Set(pr[i]); }
void Union(int i, int j)
{
    i = Set(i), j = Set(j);
    if (i == j) return;
    if (sz[i] > sz[j]) swap(i, j);
    sz[j] += sz[i];
    ok[j] = max(ok[j], ok[i]);
    pr[i] = j;
}
namespace Solve1
{
    int edge[maxN][maxN];
    bool areadj[maxN][maxN];
    int Count(int s, int l, int r)
    {
        int ans = 0;
        vector<int> q;
        for (int i = l; i <= r; ++i)
            q.push_back(edge[s][i]);
        for (int i = 0; i < n - 1; ++i)
            if ((i < l || r < i) && i != s)
            {
                q.push_back(edge[n - 1][i]);
                ans -= areadj[n - 1][i];
            }
        q.push_back(edge[n - 1][l]);
        ans -= areadj[n - 1][l];
        return ans += Query(q);
    }
    void Add(int s, int l, int r)
    {
        int cnt = Count(s, l, r);
        if (cnt == 0) return;
        if (cnt == r - l + 1)
        {
            for (int i = l; i <= r; ++i)
                areadj[s][i] = areadj[i][s] = true;
            return;
        }
        int m = l + (r - l) / 2;
        Add(s, l, m);
        Add(s, m + 1, r);
    }
    vector<int> find_roads(int n_, vector<int> us, vector<int> vs)
    {
        n = n_;
        for (int i = 0; i < us.size(); ++i)
            edge[us[i]][vs[i]] = edge[vs[i]][us[i]] = i;
        vector<bool> is(n - 1);
        vector<int> q;
        for (int i = 0; i + 1 < n - 1; ++i)
            q.push_back(edge[i][i + 1]);
        vector<int> qans(n - 1);
        for (int i = 0; i < n - 1; ++i)
        {
            q.push_back(edge[n - 1][i]);
            qans[i] = Query(q);
            q.pop_back();
        }
        int mx = *max_element(qans.begin(), qans.end());
        for (int i = 0; i < n - 1; ++i)
            if (qans[i] == mx)
                areadj[i][n - 1] = areadj[n - 1][i] = true;
        // Find edges adj. to n - 1
        for (int v = 1; v < n - 1; ++v)
            Add(v, 0, v - 1);
        vector<int> res;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (areadj[i][j])
                    res.push_back(edge[i][j]);
        return res;
    }
}
vector<int> find_roads(int n_, vector<int> us, vector<int> vs)
{
    n = n_;
    if (us.size() == (n * (n - 1)) / 2)
        return Solve1::find_roads(n, us, vs);
    int m = us.size();
    fill(gold, gold + m, -1);
    for (int i = 0; i < m; ++i)
    {
        MakeSet(i);
        nei[us[i]].push_back({vs[i], i});
        nei[vs[i]].push_back({us[i], i});
    }
    DFS(0, {-1, -1});
    // for (int i = 0; i < n; ++i)
        // cerr << "fup[" << i << "] = " << fup[i].to << '\n';
    int dfsans = Query(dfsq);
    for (int i = 0; i < m; ++i)
        if (in[us[i]] > in[vs[i]])
            swap(us[i], vs[i]);
    for (int i = 0; i < m; ++i)
    {
        int u = us[i], v = vs[i];
        if (fup[v] == -1 || in[fup[v]] > in[u]) // Is a birdge.
        {
            gold[i] = 1;
            continue;
        }
        if (par[v] == u) continue;
        while (true)
        {
            int backe = i, dfse = par[v].ind;
            if (Set(backe) == Set(dfse))
            {}
            else if (ok[Set(backe)] && ok[Set(dfse)])
            {}
            else
            {
                // cerr << dfse << ' ' << backe << '\n';
                int j = find(dfsq.begin(), dfsq.end(), dfse) - dfsq.begin();
                dfsq[j] = backe;
                int curans = Query(dfsq);
                if (curans == dfsans)
                {
                    same[backe].push_back(dfse);
                    same[dfse].push_back(backe);
                    Union(dfse, backe);
                }
                else if (curans > dfsans)
                {
                    gold[backe] = 1, gold[dfse] = 0;
                    ok[Set(backe)] = ok[Set(dfse)] = 1;
                }
                else
                {
                    gold[backe] = 0, gold[dfse] = 1;
                    ok[Set(backe)] = ok[Set(dfse)] = 1;
                }
                dfsq[j] = dfse;
            }
            if ((v = par[v]) == u) break;
        }
    }
    for (int i = 0; i < m; ++i)
        if (gold[i] != -1)
            DFS1(i);
    vector<int> ans;
    for (int i = 0; i < m; ++i)
        if (gold[i] == 1)
            ans.push_back(i);
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> Solve1::find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:116:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < us.size(); ++i)
                         ~~^~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:147:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (us.size() == (n * (n - 1)) / 2)
         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30