Submission #1116282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116282		ro9669	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	279 ms	47552 KiB

riggedroads

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(3e5)+7;

int n , m;
vector<int> g[maxN];
ii E[maxN];
bool used[maxN];
int fa[maxN] , nxt[maxN] , p[maxN] , h[maxN] , res[maxN] , cur = 0;

void dfs(int u , int par){
    for (int id : g[u]){
        int v = u ^ (E[id].fi ^ E[id].se);
        if (v != par){
            p[v] = id;
            h[v] = h[u] + 1;
            dfs(v , u);
        }
    }
}

int root(int x){
    if (fa[x] < 0) return x; else return fa[x] = root(fa[x]);
}

void unite(int u , int v){
    u = root(u);
    v = root(v);
    if (u == v) return;
    if (-fa[u] < -fa[v]) swap(u , v);
    fa[u] += fa[v];
    fa[v] = u;
    if (h[nxt[u]] > h[nxt[v]]) nxt[u] = nxt[v];
}

vector<int> pos;

void get(int u , int v){
    pos.clear();
    u = root(u);
    v = root(v);
    while (u != v){
        if (h[u] > h[v]) swap(u , v);
        int id = p[v];
        if (res[id] == 0) pos.push_back(id);
        int nxt_v = v ^ (E[id].fi ^ E[id].se);
        unite(v , nxt_v);
        v = nxt[root(v)];
    }
}

void solve(){
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i++){
        int u , v;
        cin >> u >> v;
        E[i] = {u , v};
    }
    for (int i = 1 ; i < n ; i++){
        int x; cin >> x;
        int u = E[x].fi;
        int v = E[x].se;
        used[x] = 1;
        g[u].push_back(x);
        g[v].push_back(x);
        //cout << E[x].fi << " " << E[x].se << '\n';
    }
    for (int i = 1 ; i <= n ; i++){
        fa[i] = -1;
        nxt[i] = i;
    }
    dfs(1 , 0);
    for (int i = 1 ; i <= m ; i++){
        if (used[i] == 0){
            get(E[i].fi , E[i].se);
            sort(all(pos));
            for (int x : pos) res[x] = ++cur;
            res[i] = ++cur;
        }
        else{
            if (res[i] == 0) res[i] = ++cur;
        }
    }
    for (int i = 1 ; i <= m ; i++) cout << res[i] << " ";
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(name".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