oj.uz

답안 #1011262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1011262 2024-06-30T08:25:08 Z c2zi6 Simurgh (IOI17_simurgh) C++14
13 / 100
 855 ms 8872 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "simurgh.h"

mt19937 rng;

namespace TEST1 {
    int n;
    VVI gp;
    VI vis;
    void dfs(int u = 0) {
        vis[u] = true;
        for (int v : gp[u]) if (!vis[v]) dfs(v);
    }
    bool istree(VPI edges) {
        gp = VVI(n);
        vis = VI(n);
        for (auto[u, v] : edges) {
            gp[u].pb(v);
            gp[v].pb(u);
        }
        dfs();
        rep(u, n) if (!vis[u]) return false;
        return true;
    }
    VI solve(int N, VI u, VI v) {
        n = N;
        int m = u.size();
        rep(s, 1<<m) {
            int cnt = 0;
            rep(i, m) if (s & (1<<i)) cnt++;
            if (cnt != n-1) continue;
            VPI edges;
            rep(i, m) if (s & (1<<i)) edges.pb({u[i], v[i]});
            if (!istree(edges)) continue;
            VI ret;
            rep(i, m) if (s & (1<<i)) ret.pb(i);
            if (count_common_roads(ret) == n-1) return ret;
        }
        return VI();
    }
};

int count_common_roads2(VI a) {
    VI ret;
    rep(i, a.size()) if (a[i]) ret.pb(i);
    return count_common_roads(ret);
}

namespace TEST2 {
    int n, m;
    VVPI gp;
    VI vis;
    VI par;
    VI parind;
    struct EDGE {
        int u, v, i;
        VI get() {
            VI ret;
            int cur = u;
            while (cur != v) {
                ret.pb(parind[cur]);
                cur = par[cur];
            }
            shuffle(all(ret), rng);
            return ret;
        }
    };
    vector<EDGE> back;
    VI op;
    void dfs(int u = 0, int p = -1, int pi = -1) {
        par[u] = p;
        parind[u] = pi;
        vis[u] = 1;
        for (auto[v, i] : gp[u]) if (i != pi) {
            if (vis[v] == 1) {
                back.pb({u, v, i});
                /*cout << "BACK: " << u << " " << v << " " << i << endl;*/
            } else if (vis[v] == 0) {
                /*cout << "SPAN: " << u << " " << v << " " << i << endl;*/
                op[i] = true;
                dfs(v, u, i);
            }
        }
        vis[u] = 2;
    }
    VVI gpa;
    VI comp;
    void dfs2(int u) {
        comp.pb(u);
        vis[u] = true;
        for (int v : gpa[u]) if (!vis[v]) {
            dfs2(v);
        }
    }
    VI solve(int N, VI U, VI V) {
        n = N;
        m = U.size();
        gp = VVPI(n);
        rep(i, m) {
            gp[U[i]].pb({V[i], i});
            gp[V[i]].pb({U[i], i});
        }
        vis = par = parind = VI(n);
        op = VI(m);
        dfs(rng()%n);
        VI tp(m);
        /*
         * 0 - unknown
         * 1 - regular
         * 2 - gold
         */
        int cnt = count_common_roads2(op);
        gpa = VVI(m);
        vis = VI(m);
        shuffle(all(back), rng);
        for (EDGE& e : back) {
            op[e.i] = true;
            for (int x : e.get()) {
                if (tp[x] && tp[e.i]) continue;

                op[x] = false;
                int cur = count_common_roads2(op);
                if (cur > cnt) {
                    tp[x] = 1;
                    tp[e.i] = 2;
                } else if (cur < cnt) {
                    tp[e.i] = 1;
                    tp[x] = 2;
                } else {
                    if (tp[e.i]) tp[x] = tp[e.i];
                    else if (tp[x]) tp[e.i] = tp[x];
                    else {
                        gpa[x].pb(e.i);
                        gpa[e.i].pb(x);
                    }
                }
                /*rep(u, m) cout << tp[u]; cout << endl;*/
                op[x] = true;
            }
            op[e.i] = false;
        }
        rep(u, m) if (!vis[u]) {
            comp = VI();
            dfs2(u);
            int t;
            for (int u : comp) if (tp[u]) t = tp[u];
            for (int u : comp) tp[u] = t;
        }
        VI ret;
        rep(i, m) if (tp[i] == 0) tp[i] = 2;
        rep(i, m) if (tp[i] == 2) ret.pb(i);
        return ret;
    }
}

VI find_roads(int N, VI U, VI V) {
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
    return TEST2::solve(N, U, V);
}

Compilation message

simurgh.cpp: In function 'bool TEST1::istree(VPI)':
simurgh.cpp:47:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |         for (auto[u, v] : edges) {
      |                  ^
simurgh.cpp: In function 'void TEST2::dfs(int, int, int)':
simurgh.cpp:104:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |         for (auto[v, i] : gp[u]) if (i != pi) {
      |                  ^
simurgh.cpp: In function 'VI TEST2::solve(int, VI, VI)':
simurgh.cpp:177:38: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  177 |             for (int u : comp) tp[u] = t;

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 444 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 344 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 344 KB correct
11 Correct 0 ms 344 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 344 KB correct
14 Correct 3 ms 348 KB correct
15 Correct 3 ms 348 KB correct
16 Correct 3 ms 348 KB correct
17 Correct 2 ms 348 KB correct
18 Correct 1 ms 440 KB correct
19 Correct 3 ms 348 KB correct
20 Correct 2 ms 344 KB correct
21 Correct 2 ms 348 KB correct
22 Incorrect 2 ms 348 KB WA in grader: NO
23 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 444 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 344 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 344 KB correct
11 Correct 0 ms 344 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 344 KB correct
14 Correct 3 ms 348 KB correct
15 Correct 3 ms 348 KB correct
16 Correct 3 ms 348 KB correct
17 Correct 2 ms 348 KB correct
18 Correct 1 ms 440 KB correct
19 Correct 3 ms 348 KB correct
20 Correct 2 ms 344 KB correct
21 Correct 2 ms 348 KB correct
22 Incorrect 2 ms 348 KB WA in grader: NO
23 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Incorrect 855 ms 8872 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 444 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 344 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 344 KB correct
11 Correct 0 ms 344 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 344 KB correct
14 Correct 3 ms 348 KB correct
15 Correct 3 ms 348 KB correct
16 Correct 3 ms 348 KB correct
17 Correct 2 ms 348 KB correct
18 Correct 1 ms 440 KB correct
19 Correct 3 ms 348 KB correct
20 Correct 2 ms 344 KB correct
21 Correct 2 ms 348 KB correct
22 Incorrect 2 ms 348 KB WA in grader: NO
23 Halted 0 ms 0 KB -