oj.uz

답안 #283862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283862 2020-08-26T08:21:06 Z ToMmyDong Simurgh (IOI17_simurgh) C++11
30 / 100
 3000 ms 8300 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());
    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);
    } 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(880301);
    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:145:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  145 |     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:242:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  242 |     while (good.size() < n - 1) {
      |            ~~~~~~~~~~~~^~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 416 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 512 KB correct
14 Correct 150 ms 512 KB correct
15 Correct 140 ms 632 KB correct
16 Correct 162 ms 632 KB correct
17 Correct 113 ms 492 KB correct
18 Correct 10 ms 384 KB correct
19 Correct 93 ms 500 KB correct
20 Correct 84 ms 384 KB correct
21 Correct 80 ms 504 KB correct
22 Correct 35 ms 384 KB correct
23 Correct 24 ms 384 KB correct
24 Correct 19 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 19 ms 384 KB correct
27 Correct 30 ms 384 KB correct
28 Correct 5 ms 384 KB correct
29 Correct 2 ms 384 KB correct
30 Correct 29 ms 416 KB correct
31 Correct 25 ms 384 KB correct
32 Correct 29 ms 504 KB correct
33 Correct 31 ms 384 KB correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 416 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 512 KB correct
14 Correct 150 ms 512 KB correct
15 Correct 140 ms 632 KB correct
16 Correct 162 ms 632 KB correct
17 Correct 113 ms 492 KB correct
18 Correct 10 ms 384 KB correct
19 Correct 93 ms 500 KB correct
20 Correct 84 ms 384 KB correct
21 Correct 80 ms 504 KB correct
22 Correct 35 ms 384 KB correct
23 Correct 24 ms 384 KB correct
24 Correct 19 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 19 ms 384 KB correct
27 Correct 30 ms 384 KB correct
28 Correct 5 ms 384 KB correct
29 Correct 2 ms 384 KB correct
30 Correct 29 ms 416 KB correct
31 Correct 25 ms 384 KB correct
32 Correct 29 ms 504 KB correct
33 Correct 31 ms 384 KB correct
34 Execution timed out 3043 ms 3092 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 3087 ms 8300 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 416 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 1 ms 512 KB correct
14 Correct 150 ms 512 KB correct
15 Correct 140 ms 632 KB correct
16 Correct 162 ms 632 KB correct
17 Correct 113 ms 492 KB correct
18 Correct 10 ms 384 KB correct
19 Correct 93 ms 500 KB correct
20 Correct 84 ms 384 KB correct
21 Correct 80 ms 504 KB correct
22 Correct 35 ms 384 KB correct
23 Correct 24 ms 384 KB correct
24 Correct 19 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 19 ms 384 KB correct
27 Correct 30 ms 384 KB correct
28 Correct 5 ms 384 KB correct
29 Correct 2 ms 384 KB correct
30 Correct 29 ms 416 KB correct
31 Correct 25 ms 384 KB correct
32 Correct 29 ms 504 KB correct
33 Correct 31 ms 384 KB correct
34 Execution timed out 3043 ms 3092 KB Time limit exceeded
35 Halted 0 ms 0 KB -