Submission #1090588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090588		Lyestria	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	345 ms	74984 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
 
using ll = long long;
const int inf = 1e9 + 100;
const ll linf = 1e18 + 100;
using vi = vector<int>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
 
// #define cerr if(0)cerr

mt19937 rnd(time(0));
 
#define TIME (clock() * 1. / CLOCKS_PER_SEC)
 
using ld = long double;
const ld PI = acosl(-1.L);
 
const int maxn = 1e6+10;
const ll mod = 998244353;

vector<pii> g[maxn];

struct DSU {
  vector<int> p;
  DSU(int n): p(n) {
    iota(all(p),0);
  }
  int f(int x){return x==p[x]?x:(p[x]=f(p[x]));}
  void u(int a,int b){
    a=f(a),b=f(b);
    if(a==b)return;
    p[b]=a;
  }
};
int dep[maxn];
int par[maxn];
int parei[maxn];
void dfs(int x, int p){
  par[x] = p;
  for(auto [y, ei] : g[x]) if(y!=p) {
    dep[y] = dep[x] + 1;
    parei[y]=ei;
    dfs(y,x);
  }
}

void solve() {
  int n,m;
  cin >> n >> m;
  vector<pii> eds;
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    a--,b--;
    eds.push_back({a,b});
  }
  set<int> spt;
  for(int i=0;i<n-1;i++){
    int x;
    cin >> x;
    spt.insert(x-1);
    auto [a,b] = eds[x-1];
    g[a].push_back({b,x-1});
    g[b].push_back({a,x-1});
  }
  dfs(0,-1);
  DSU dsu(n);
  int cur = 0;
  vector<int> ans(m,-1);
  for(int i=0;i<m;i++){
    if(ans[i]!=-1)continue;
    auto [a,b] = eds[i];
    if(spt.count(i)) {
      ans[i]=cur++;
      auto [a,b] = eds[i];
      if(dep[a]>dep[b])swap(a,b);
      dsu.u(a,b);
      // cerr << i << " " << ans[i] << endl;
      continue;
    }
    a=dsu.f(a),b=dsu.f(b);
    vector<int> ve;
    while(a!=b) {
      if(dep[a]>dep[b]) {
        dsu.u(par[a],a);
        ve.push_back(parei[a]);
        a=dsu.f(a);
      }
      else {
        dsu.u(par[b],b);
        ve.push_back(parei[b]);
        b=dsu.f(b);
      }
    }
    sort(all(ve));
    for(int i=0;i<ve.size();i++){
      // cerr << ve[i] << " " << cur+i << endl;
      ans[ve[i]]=cur+i;
    }
    cur+=ve.size();
    ans[i]=cur++;
  }
  for(int i=0;i<m;i++)cout << ans[i]+1 << " \n"[i==m-1];
}
 
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	cout << fixed;
	cout.precision(9);
  solve();
}

Compilation message (stderr)

riggedroads.cpp: In function 'void solve()':
riggedroads.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<ve.size();i++){
      |                 ~^~~~~~~~~~

• 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