Submission #774817

#	Time	Username	Problem	Language	Result	Execution time	Memory
774817		Cookie	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	288 ms	66828 KiB

riggedroads

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("HAMMING.INP");
ofstream fout("HAMMING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e18 + 7, inf = 1e16;
const int mxn = 3e5 + 5, sq = 400;
int n, e;
vt<pii>adj[mxn + 1];
bool ok[mxn + 1];
int special[mxn + 1], dep[mxn + 1], up[mxn + 1][19], toedge[mxn + 1], ans[mxn + 1];
pii edge[mxn + 1];
void dfs(int s, int pre){
    for(auto [i, id]: adj[s]){
        if(i != pre){
            dep[i] = dep[s] + 1;
            up[i][0] = s; toedge[i] = id;
            dfs(i, s);
        }
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v])swap(u, v);;
    int k = dep[u] - dep[v];
    for(int i = 0; i < 19; i++){
        if(k & (1 << i)){
            u = up[u][i];
        }
    }
    if(u == v)return(u);
    for(int i = 18; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i]; v = up[v][i];
        }
    }
    return(up[u][0]);
}
struct DSU{
    int p[mxn + 1], sz[mxn + 1];    
    void init(){
        for(int i = 1; i <= mxn; i++){
            p[i] = i; sz[i] = 1;
        }
    }
    int fp(int u){
        if(p[u] == u)return(u);
        return(p[u] = fp(p[u]));
    }
    void unon(int a, int b){
        a = fp(a); b = fp(b);
        if(a == b)return;
        if(dep[a] > dep[b])swap(a, b);
        p[b] = a; sz[a] += sz[b];
    }
};
DSU dsu;
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> e;
    dsu.init();
    for(int i = 0; i < e; i++){
        cin >> edge[i].fi >> edge[i].se; ans[i] = -1;
    }
    for(int i = 1; i < n; i++){
        cin >> special[i]; special[i]--; auto [u, v] = edge[special[i]]; ok[special[i]] = 1;
        adj[u].pb(make_pair(v, special[i])); adj[v].pb(make_pair(u, special[i])); 
    }
    dfs(1, -1);
    for(int i = 1; i < 19; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    int mn = 1;
    for(int i = 0; i < e; i++){
        auto [u, v] = edge[i];
        if(ans[i] != -1)continue;
        if(ok[i]){
            dsu.unon(u, v);
            ans[i] = mn++; continue;
        }
        int l = lca(u, v); 
       
        vt<int>change;
        while(1){
            int tou = dsu.fp(u); 
            if(dep[tou] <= dep[l])break;
            change.pb(toedge[tou]); 
            auto [uu, vv] = edge[toedge[tou]];
            dsu.unon(uu, vv);
            
        }
        
        while(1){
            int tov = dsu.fp(v);
            if(dep[tov] <= dep[l])break;
            change.pb(toedge[tov]); 
            auto [uu, vv] = edge[toedge[tov]];
            
            dsu.unon(uu, vv);
            //cout << tov << " ";
        }
        
        sort(change.begin(), change.end());
        for(auto j: change){
            ans[j] = mn++;
        }
        ans[i] = mn++;
        
    }
    for(int i = 0; i < e; i++){
        cout << ans[i] << " ";
    }
    return(0);
}

Compilation message (stderr)

riggedroads.cpp: In function 'void dfs(int, int)':
riggedroads.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [i, id]: adj[s]){
      |              ^
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:82:47: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |         cin >> special[i]; special[i]--; auto [u, v] = edge[special[i]]; ok[special[i]] = 1;
      |                                               ^
riggedroads.cpp:93:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |         auto [u, v] = edge[i];
      |              ^
riggedroads.cpp:106:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |             auto [uu, vv] = edge[toedge[tou]];
      |                  ^
riggedroads.cpp:115:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |             auto [uu, vv] = edge[toedge[tov]];
      |                  ^

• 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