Submission #877205

#	Time	Username	Problem	Language	Result	Execution time	Memory
877205		SyruLoveNewTechnology	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	206 ms	39740 KiB

riggedroads

//SyruLoveNewTechnology
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rand(const int &l, const int &r) {
    return rng() % (r - l + 1) + l;
}

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

const int MAX = 300005;

int N, M;
int a[MAX], b[MAX];
int r1[MAX];
int w[MAX];
int par[MAX];
int p[15];
bool check[MAX];
int parent[MAX];
vector<int> adj[MAX];
int nex[MAX], h[MAX], t;

void read() {
    cin >> N >> M;
    for(int i = 1; i <= M; ++i)
        cin >> a[i] >> b[i];
    for(int i = 1; i < N; ++i)
        cin >> r1[i];
}

int root(int u) {
    if(par[u] < 0)
        return u;
    par[u] = root(par[u]);
    return par[u];
}

bool join(int u, int v) {
    u = root(u);
    v = root(v);
    if(u == v)
        return false;
    if(par[u] > par[v])
        swap(par[u], par[v]);
    par[u] += par[v];
    par[v] = u;
    return true;
}

bool check1() {
    fill(par + 1, par + N + 1, -1);
    for(int i = 1; i <= M; ++i)
        p[w[i]] = i;
    for(int i = 1; i <= M; ++i) {
        bool c = join(a[p[i]], b[p[i]]);
        if(check[p[i]] != c)
            return false;
    }
    return true;
}

void sub1() {
    for(int i = 1; i <= M; ++i)
        w[i] = i;
    for(int i = 1; i < N; ++i)
        check[r1[i]] = true;
    if(check1()) {
        for(int i = 1; i <= M; ++i)
            cout << w[i] << ' ';
        cout << '\n';
        return;
    }
    while(next_permutation(w + 1, w + M + 1)) {
        if(check1()) {
            for(int i = 1; i <= M; ++i)
                cout << w[i] << ' ';
            cout << '\n';
            return;
        }
    }
}

void dfs(int u, int p) {
    h[u] = h[p] + 1;
    for(int i : adj[u]) {
        int v = u ^ a[i] ^ b[i];
        if(v != p) {
            parent[v] = i;
            dfs(v, u);
        }
    }
}

void add(int i) {
    if(parent[b[i]] == i)
        swap(a[i], b[i]);
    nex[a[i]] = b[i];
}

int ROOT(int u) {
    if(nex[u] == u)
        return u;
    nex[u] = ROOT(nex[u]);
    return nex[u];
}

void solve() {
    for(int i = 1; i < N; ++i) {
        check[r1[i]] = true;
        adj[a[r1[i]]].emplace_back(r1[i]);
        adj[b[r1[i]]].emplace_back(r1[i]);
    }
    dfs(1, 0);
    for(int i = 1; i <= N; ++i)
        nex[i] = i;
    for(int i = 1; i <= M; ++i)
        if(w[i] == 0) {
            if(check[i]) {
                ++t;
                w[i] = t;
                add(i);
            }
            else {
                int ra = ROOT(a[i]);
                int rb = ROOT(b[i]);
                if(ra == rb) {
                    ++t;
                    w[i] = t;
                }
                else {
                    vector<int> q;
                    a[i] = nex[a[i]];
                    b[i] = nex[b[i]];
                    while(a[i] != b[i]) {
                        if(h[a[i]] < h[b[i]])
                            swap(a[i], b[i]);
                        q.emplace_back(parent[a[i]]);
                        add(parent[a[i]]);
                        a[i] = ROOT(a[i]);
                    }
                    sort(q.begin(), q.end());
                    for(int i : q) {
                        ++t;
                        w[i] = t;
                    }
                    ++t;
                    w[i] = t;
                }
            }
        }
    for(int i = 1; i <= M; ++i)
        cout << w[i] << ' ';
    cout << '\n';
}

main() {
    fre();
    read();
    if(N <= 9 && M <= 9)
        sub1();
    else
        solve();
}

Compilation message (stderr)

riggedroads.cpp:167:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  167 | main() {
      | ^~~~
riggedroads.cpp: In function 'void fre()':
riggedroads.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen("ZONING.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen("ZONING.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32