Submission #1250591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250591		quocbaoo	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	335 ms	59516 KiB

riggedroads

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=3e5;
int kq[N+5],cha[N+5],h[N+5],sz[N+5],pos[N+5];
int cnt=0,par[N+6],dp[N+5],a[N+5],b[N+5],r[N+5];
vector<pair<int,int>> g[N+5];
multiset<int> st;vector<int> vec;
void dfs(int i,int pa){
    sz[i]=1;
    for (auto j:g[i]){
        if (j.fi==pa) continue;
        h[j.fi]=h[i]+1;cha[j.fi]=i;
        dfs(j.fi,i);
        sz[i]+=sz[j.fi];
    }
}
void hld(int i,int pa){
    cnt++;pos[i]=cnt;
    int ma=0,big=0,lex;
    for (auto j:g[i]){
        if (j.fi==pa) continue;
        if (sz[j.fi]>ma){
            ma=sz[j.fi];big=j.fi;lex=j.se;
        }
    }
    if (big!=0){
        par[big]=par[i];st.insert(cnt+1);
        dp[cnt+1]=lex;
        hld(big,i);
    }
    for (auto j:g[i]){
        if (j.fi==pa||j.fi==big) continue;
        par[j.fi]=j.fi;
        st.insert(cnt+1);dp[cnt+1]=j.se;
        hld(j.fi,i);
    }
}
void gop(int u,int v){
    while (par[u]!=par[v]){
        if (h[par[u]]<h[par[v]]) swap(u,v);
        auto it=st.lower_bound(pos[par[u]]);
        while (it!=st.end()){
            auto it1=it;it1++;
            if ((*it)>pos[u]) break;
            vec.push_back(dp[(*it)]);
            st.erase(it);it=it1;
        }
        u=cha[par[u]];
    }
    if (h[u]<h[v]) swap(u,v);
    if (u==v) return;
    auto it=st.lower_bound(pos[v]+1);
    while (it!=st.end()){
        auto it1=it;it1++;
        if ((*it)>pos[u]) break;
        vec.push_back(dp[(*it)]);
        st.erase(it);it=it1;
    }
}
int main(){
    if (fopen("rigger.inp","r")){
        freopen("rigger.inp","r",stdin);
        freopen("rigger.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    for (int i=1;i<=m;i++) cin>>a[i]>>b[i];
    for (int i=1;i<n;i++){
        cin>>r[i];
        g[a[r[i]]].push_back({b[r[i]],r[i]});
        g[b[r[i]]].push_back({a[r[i]],r[i]});
    }
    dfs(1,1);
    par[1]=1;
    hld(1,1);
    int dem=0;
    for (int i=1;i<=m;i++){
        vec.clear();
        gop(a[i],b[i]);
        sort(vec.begin(),vec.end());
        for (auto j:vec){
            dem++;kq[j]=dem;
        }
        if (kq[i]>0) {
            cout<<kq[i]<<" ";
            continue;
        }
        dem++;kq[i]=dem;
        cout<<kq[i]<<" ";
    }
}

Compilation message (stderr)

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