oj.uz

답안 #283856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283856 2020-08-26T08:13:25 Z ToMmyDong Simurgh (IOI17_simurgh) C++11
0 / 100
 1492 ms 1048580 KB 
#include "simurgh.h"
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define SZ(i) int(i.size())
#define ALL(i) i.begin(), i.end()
#define MEM(i,a) memset(i, (a), sizeof(i))
#define X first
#define Y second
#define eb emplace_back
#define pb push_back
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do (T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<", ";_do(y...);}
template<typename IT> ostream& __printRng (ostream &os, IT bg, IT ed) {
    for (IT it=bg; it!=ed; it++) {
        if (it!=bg) os << "," << *it;
        else os << "{" << *it;
    }
    return os << "}";
}
template<typename T> ostream &operator << (ostream &os, const pair<T,T> &v) {
    return os << "{" << v.X <<","<<v.Y<<"}";

}
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) {
    return __printRng(os, ALL(v));
}
template<typename T> ostream &operator << (ostream &os, const set<T> &v) {
    return __printRng(os, ALL(v));
}
#else
#define debug(...)
#endif

const int MAXN = 502;
vector<pii> edge[MAXN];
vector<pii> euv;

int m, n;
set<int> rem, bad, good;

int pid[MAXN], fat[MAXN], dep[MAXN];
void dfs_c (int nd, int par, vector<int> &cid) {
    fat[nd] = par;
    dep[nd] = dep[par] + 1;
    for (auto p : edge[nd]) {
        int u, id;
        tie(u, id) = p;
        if (rem.count(id) == 0) continue;
        if (u != par) {
            if (dep[u] != 0) {
                if (dep[u] > dep[nd]) continue;
                vector<int> nw;
                nw.eb(id);
                int cur = nd;
                while (cur != u) {
                    nw.eb(pid[cur]);
                    cur = fat[cur];
                }
                cid = nw;
            } else {
                pid[u] = id;
                dfs_c(u, nd, cid);
            }
        }
    }
}

vector<int> rem_cycle () {
    MEM(pid, -1);
    MEM(dep, 0);
    for (int i=0; i<n; i++) {
        if (pid[i] == -1) {
            vector<int> cur;
            dfs_c(i, i, cur);
            if (cur.size()) return cur;
        }
    }
    return vector<int>();
}

int djs[MAXN];

void init () {
    for (int i=0; i<n; i++) {
        djs[i] = i;
    }
}

int fnd (int x) {
    return x == djs[x] ? x : djs[x] = fnd(djs[x]);
}

bool mrg (int x, int y) {
    x = fnd(x), y = fnd(y);
    if (x == y) return false;
    djs[x] = y;
    return true;
}

vector<int> span (vector<int> cyc) {
    init();
    for (int v : cyc) {
        mrg(euv[v].X, euv[v].Y);
    }
    vector<int> res;
    for (int i=0; i<m; i++) {
        if (mrg(euv[i].X, euv[i].Y)) {
            res.eb(i);
        }
    }
    return res;
}

set<int> trees;
void dfs_t (int nd, int par) {
    dep[nd] = dep[par] + 1;
    fat[nd] = par;
    for (auto p : edge[nd]) {
        int u, id;
        tie(u, id) = p;
        if (trees.count(id) == 0) continue;
        if (u == par) continue;
        pid[u] = id;
        dfs_t(u, nd);
    }

}

int count_common_roads(const std::set<int> &r) {
    vector<int> v;
    for (auto e : r) v.eb(e);
    return count_common_roads(v);
}

void srem () {
    init();
    debug(good.size(), rem.size());
    if (good.size() + rem.size() == n-1) {
        for (int v : rem) {
            good.insert(v);
        }
        rem.clear();
        return;
    }
    for (int g : good) {
        trees.insert(g);
        mrg(euv[g].X, euv[g].Y);
    }
    int fail = -1;
    for (int g : rem) {
        if (mrg(euv[g].X, euv[g].Y)) {
            trees.insert(g);
        } else {
            fail = g;
        }
    }
    assert(fail != -1);
    dfs_t(0, 0);
    int swp = -1;
    int u, v;
    tie(u, v) = euv[fail];

    while (u != v) {
        if (dep[u] > dep[v]) swap(u, v);
        if (good.count(pid[v])) swp = pid[v];
        v = fat[v];
    }
    assert(swp != -1);

    int org = count_common_roads(trees);
    trees.erase(swp);
    trees.insert(fail);
    int nw = count_common_roads(trees);
    if (nw == org) {
        good.insert(fail);
    } else {
        bad.insert(fail);
    }
    rem.erase(fail);
}

std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
    n = _n;
    m = SZ(u);

    
    srand(time(0));
    vector<int> perm(n);
    iota(ALL(perm), 0);
    random_shuffle(ALL(perm));

    for (int i=0; i<m; i++) {
        u[i] = perm[u[i]];
        v[i] = perm[v[i]];
        rem.insert(i);
        euv.eb(u[i], v[i]);
        edge[u[i]].eb(v[i], i);
        edge[v[i]].eb(u[i], i);
    }


    debug(euv);
    while (true) {
        vector<int> cyc = rem_cycle();
        if (cyc.empty()) break;
        debug(cyc);
        while(cyc.size() <= 2);

        vector<int> sp = span(cyc);
        vector<pii> res;
        int csz = SZ(cyc);
        for (int i=0; i<csz; i++) {
            for (int j=0; j<csz; j++) {
                if (i != j) sp.eb(cyc[j]);
            }
            res.eb(count_common_roads(sp), cyc[i]);
            for (int j=0; j<csz-1; j++) sp.pop_back();
        }
        sort(ALL(res));
        for (auto p : res) {
            if (p.X == res.back().X) {
                bad.insert(p.Y);
            } else {
                good.insert(p.Y);
            }
            rem.erase(p.Y);
        }
        debug(res);
    }
    debug(good);
    debug(bad);
    debug(rem);

    while (good.size() < n - 1) {
        srem();
    }

    vector<int> ans;
    for (int x : good) ans.eb(x);
    return ans;
}

Compilation message

simurgh.cpp: In function 'void srem()':
simurgh.cpp:144:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  144 |     if (good.size() + rem.size() == n-1) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:240:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  240 |     while (good.size() < n - 1) {
      |            ~~~~~~~~~~~~^~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Runtime error 1492 ms 1048580 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Runtime error 1492 ms 1048580 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Runtime error 1492 ms 1048580 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB correct
2 Runtime error 1099 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Runtime error 1492 ms 1048580 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -