oj.uz

Submission #877181

# Submission time Handle Problem Language Result Execution time Memory
877181 2023-11-23T02:53:47 Z logn Rigged Roads (NOI19_riggedroads) C++14
58 / 100
 2000 ms 56492 KB 
#include <bits/stdc++.h>                                                                                                                                                                                      //Logm
using namespace std;
#define int long long
#define II pair<int,int>
#define fi first
#define se second

const int N = 3e5+5;
int n, m;

II e[N];
int idx[N];
bool spec[N];

int par[N], rak[N];
void init(int n) {
    for (int i = 1; i <= n; ++i) {
        par[i] = i;
        rak[i] = 0;
    }
}
int find(int u) {
    if (par[u] != u) par[u] = find(par[u]);
    return par[u];
}
bool join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return 0;
    if (rak[u] == rak[v]) ++rak[u];
    if (rak[u] < rak[v]) par[u] = v;
    else par[v] = u;
    return 1;
}

namespace sub1 {
    void solve() {
        int p[m];
        for (int i = 0; i < m; ++i) p[i] = i + 1;
        
        vector<int> ans;
        do {
            init(n);
            bool flag = 0;
            for (int i = 0; i < m; ++i) {
                if (spec[p[i]]) {
                    if (!join(e[p[i]].fi, e[p[i]].se)) {
                        flag = 1;
                        break;
                    }
                } else {
                    if (join(e[p[i]].fi, e[p[i]].se)) {
                        flag = 1;
                        break;
                    }
                }
            }
            if (flag) continue;

            vector<int> res(m);
            for (int i = 0; i < m; ++i)
                res[p[i] - 1] = i + 1;
            
            if (ans.empty()) ans = res;
            else ans = min(ans, res);
        } while (next_permutation(p, p + m));
        
        for (int i: ans) cout << i << ' ';
        exit(0);
    }
}

namespace sub2 {
    vector<II> adj[N];
    int ans[N];

    int index;
    II par[N];
    int dep[N];
     
    void build(int u) {
        for (II ed: adj[u]) {
            int v = ed.fi, id = ed.se;
            if (v != par[u].fi) {
                par[v] = II(u, id);
                dep[v] = dep[u] + 1;
                build(v);
            }
        }
    }
    void getpath(int u, int v, vector<int> &path) {
        if (dep[u] < dep[v]) swap(u, v);

        while (dep[u] > dep[v]) {
            path.push_back(par[u].se);
            u = par[u].fi;
        }
        if (u == v) return;

        while (u != v) {
            path.push_back(par[u].se);
            u = par[u].fi;
            path.push_back(par[v].se);
            v = par[v].fi;
        }
    }

    void solve() {
        for (int i = 1; i < n; ++i) {
            int u = e[idx[i]].fi, v = e[idx[i]].se;
            adj[u].push_back(II(v, idx[i]));
            adj[v].push_back(II(u, idx[i]));
        }

        build(1);

        for (int i = 1; i <= m; ++i) {
            if (spec[i]) {
                if (ans[i] == 0) ans[i] = ++index;
            } else {
                int u = e[i].fi, v = e[i].se;
                // đường đi từ u đến v trên cây khung phải được đánh số nhỏ hơn
                vector<int> path;
                getpath(u, v, path);
                sort(path.begin(), path.end());
                for (int x: path) {
                    if (ans[x] == 0) ans[x] = ++index;
                }
                ans[i] = ++index;
            }
        }

        for (int i = 1; i <= m; ++i)
            cout << ans[i] << ' ';
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("ZONING.inp", "r")) {
        freopen("ZONING.inp", "r", stdin);
        freopen("ZONING.out", "w", stdout);
    }

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        e[i] = II(u, v);
    }

    for (int i = 1; i < n; ++i) {
        cin >> idx[i];
        spec[idx[i]] = 1;
    }

    if (m <= 9) sub1::solve();

    sub2::solve();

    return 0;
}

Compilation message

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen("ZONING.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen("ZONING.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14684 KB Output is correct
2 Correct 25 ms 14684 KB Output is correct
3 Correct 21 ms 14680 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14684 KB Output is correct
2 Correct 25 ms 14684 KB Output is correct
3 Correct 21 ms 14680 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12904 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24524 KB Output is correct
2 Correct 57 ms 29756 KB Output is correct
3 Correct 66 ms 20392 KB Output is correct
4 Correct 86 ms 39188 KB Output is correct
5 Correct 91 ms 40608 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 33368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 46412 KB Output is correct
2 Correct 171 ms 52428 KB Output is correct
3 Correct 38 ms 26828 KB Output is correct
4 Correct 60 ms 31692 KB Output is correct
5 Correct 202 ms 56492 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 39500 KB Output is correct
2 Correct 57 ms 31688 KB Output is correct
3 Correct 190 ms 48344 KB Output is correct
4 Correct 196 ms 45008 KB Output is correct
5 Correct 12 ms 17144 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14684 KB Output is correct
2 Correct 25 ms 14684 KB Output is correct
3 Correct 21 ms 14680 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12904 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 32 ms 24524 KB Output is correct
10 Correct 57 ms 29756 KB Output is correct
11 Correct 66 ms 20392 KB Output is correct
12 Correct 86 ms 39188 KB Output is correct
13 Correct 91 ms 40608 KB Output is correct
14 Execution timed out 2086 ms 33368 KB Time limit exceeded
15 Halted 0 ms 0 KB -