oj.uz

답안 #283866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283866 2020-08-26T08:27:54 Z ToMmyDong Simurgh (IOI17_simurgh) C++11
30 / 100
 3000 ms 7796 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, good;
bool is_good[MAXN*MAXN];
bool is_rem[MAXN*MAXN];

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 (is_rem[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], sz[MAXN];

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

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;
    if (sz[x] > sz[y]) swap(x, y);
    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());
    trees.clear();
    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;
        }
    }
    debug(trees);
    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);
    }
    rem.erase(fail);
    is_rem[fail] = false;
}

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

    for (int i=0; i<m; i++) {
        rem.insert(i);
        is_rem[i] = true;
        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);
        assert(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) {
                good.insert(p.Y);
            }
            rem.erase(p.Y);
            is_rem[p.Y] = false;
        }
        debug(res);
    }
    debug(good);
    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:149:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  149 |     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:236:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  236 |     while (good.size() < n - 1) {
      |            ~~~~~~~~~~~~^~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 288 KB correct
3 Correct 1 ms 288 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 1 ms 384 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 1 ms 384 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 384 KB correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 288 KB correct
3 Correct 1 ms 288 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 1 ms 384 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 1 ms 384 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 82 ms 512 KB correct
15 Correct 83 ms 608 KB correct
16 Correct 88 ms 504 KB correct
17 Correct 64 ms 504 KB correct
18 Correct 7 ms 448 KB correct
19 Correct 57 ms 384 KB correct
20 Correct 51 ms 504 KB correct
21 Correct 44 ms 384 KB correct
22 Correct 23 ms 384 KB correct
23 Correct 16 ms 384 KB correct
24 Correct 12 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 13 ms 384 KB correct
27 Correct 15 ms 384 KB correct
28 Correct 4 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 19 ms 384 KB correct
31 Correct 23 ms 384 KB correct
32 Correct 16 ms 384 KB correct
33 Correct 15 ms 384 KB correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 288 KB correct
3 Correct 1 ms 288 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 1 ms 384 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 1 ms 384 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 82 ms 512 KB correct
15 Correct 83 ms 608 KB correct
16 Correct 88 ms 504 KB correct
17 Correct 64 ms 504 KB correct
18 Correct 7 ms 448 KB correct
19 Correct 57 ms 384 KB correct
20 Correct 51 ms 504 KB correct
21 Correct 44 ms 384 KB correct
22 Correct 23 ms 384 KB correct
23 Correct 16 ms 384 KB correct
24 Correct 12 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 13 ms 384 KB correct
27 Correct 15 ms 384 KB correct
28 Correct 4 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 19 ms 384 KB correct
31 Correct 23 ms 384 KB correct
32 Correct 16 ms 384 KB correct
33 Correct 15 ms 384 KB correct
34 Execution timed out 3074 ms 2924 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Execution timed out 3050 ms 7796 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 288 KB correct
3 Correct 1 ms 288 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 1 ms 384 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 1 ms 384 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 82 ms 512 KB correct
15 Correct 83 ms 608 KB correct
16 Correct 88 ms 504 KB correct
17 Correct 64 ms 504 KB correct
18 Correct 7 ms 448 KB correct
19 Correct 57 ms 384 KB correct
20 Correct 51 ms 504 KB correct
21 Correct 44 ms 384 KB correct
22 Correct 23 ms 384 KB correct
23 Correct 16 ms 384 KB correct
24 Correct 12 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 13 ms 384 KB correct
27 Correct 15 ms 384 KB correct
28 Correct 4 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 19 ms 384 KB correct
31 Correct 23 ms 384 KB correct
32 Correct 16 ms 384 KB correct
33 Correct 15 ms 384 KB correct
34 Execution timed out 3074 ms 2924 KB Time limit exceeded
35 Halted 0 ms 0 KB -