oj.uz

Submission #283864

# Submission time Handle Problem Language Result Execution time Memory
283864 2020-08-26T08:24:45 Z ToMmyDong Simurgh (IOI17_simurgh) C++11
30 / 100
 3000 ms 7660 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;

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);
    }
    rem.erase(fail);
}

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);
        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);
        }
        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: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:229:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  229 |     while (good.size() < n - 1) {
      |            ~~~~~~~~~~~~^~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB correct
2 Correct 1 ms 288 KB correct
3 Correct 0 ms 384 KB correct
4 Correct 1 ms 308 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 308 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 1 ms 384 KB correct
11 Correct 1 ms 288 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 1 ms 384 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB correct
2 Correct 1 ms 288 KB correct
3 Correct 0 ms 384 KB correct
4 Correct 1 ms 308 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 308 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 1 ms 384 KB correct
11 Correct 1 ms 288 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 124 ms 500 KB correct
15 Correct 131 ms 512 KB correct
16 Correct 132 ms 512 KB correct
17 Correct 100 ms 384 KB correct
18 Correct 10 ms 432 KB correct
19 Correct 119 ms 384 KB correct
20 Correct 76 ms 384 KB correct
21 Correct 65 ms 384 KB correct
22 Correct 43 ms 384 KB correct
23 Correct 25 ms 384 KB correct
24 Correct 18 ms 384 KB correct
25 Correct 1 ms 360 KB correct
26 Correct 34 ms 384 KB correct
27 Correct 24 ms 384 KB correct
28 Correct 5 ms 384 KB correct
29 Correct 2 ms 384 KB correct
30 Correct 30 ms 384 KB correct
31 Correct 27 ms 444 KB correct
32 Correct 23 ms 384 KB correct
33 Correct 22 ms 384 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB correct
2 Correct 1 ms 288 KB correct
3 Correct 0 ms 384 KB correct
4 Correct 1 ms 308 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 308 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 1 ms 384 KB correct
11 Correct 1 ms 288 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 124 ms 500 KB correct
15 Correct 131 ms 512 KB correct
16 Correct 132 ms 512 KB correct
17 Correct 100 ms 384 KB correct
18 Correct 10 ms 432 KB correct
19 Correct 119 ms 384 KB correct
20 Correct 76 ms 384 KB correct
21 Correct 65 ms 384 KB correct
22 Correct 43 ms 384 KB correct
23 Correct 25 ms 384 KB correct
24 Correct 18 ms 384 KB correct
25 Correct 1 ms 360 KB correct
26 Correct 34 ms 384 KB correct
27 Correct 24 ms 384 KB correct
28 Correct 5 ms 384 KB correct
29 Correct 2 ms 384 KB correct
30 Correct 30 ms 384 KB correct
31 Correct 27 ms 444 KB correct
32 Correct 23 ms 384 KB correct
33 Correct 22 ms 384 KB correct
34 Execution timed out 3062 ms 2940 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Execution timed out 3006 ms 7660 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB correct
2 Correct 1 ms 288 KB correct
3 Correct 0 ms 384 KB correct
4 Correct 1 ms 308 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 308 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 1 ms 384 KB correct
11 Correct 1 ms 288 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 124 ms 500 KB correct
15 Correct 131 ms 512 KB correct
16 Correct 132 ms 512 KB correct
17 Correct 100 ms 384 KB correct
18 Correct 10 ms 432 KB correct
19 Correct 119 ms 384 KB correct
20 Correct 76 ms 384 KB correct
21 Correct 65 ms 384 KB correct
22 Correct 43 ms 384 KB correct
23 Correct 25 ms 384 KB correct
24 Correct 18 ms 384 KB correct
25 Correct 1 ms 360 KB correct
26 Correct 34 ms 384 KB correct
27 Correct 24 ms 384 KB correct
28 Correct 5 ms 384 KB correct
29 Correct 2 ms 384 KB correct
30 Correct 30 ms 384 KB correct
31 Correct 27 ms 444 KB correct
32 Correct 23 ms 384 KB correct
33 Correct 22 ms 384 KB correct
34 Execution timed out 3062 ms 2940 KB Time limit exceeded
35 Halted 0 ms 0 KB -