Submission #842179

#	Time	Username	Problem	Language	Result	Execution time	Memory
842179		8pete8	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	314 ms	111724 KiB

riggedroads

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
//#include "supertrees.h"
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const int mxn=3*1e5,mod=998244353,lg=20,root=80,inf=1e9;
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
int n,m;
vector<pii>adj[mxn+10];
int h[mxn+10],ans[mxn+10],cut[mxn+10];
pii up[mxn+10][lg+10];
void dfs(int cur,int p){
    for(auto i:adj[cur]){
        if(i.f==p)continue;
        h[i.f]=h[cur]+1;
        up[i.f][0].f=cur;
        up[i.f][0].s=i.s;
        dfs(i.f,cur);
    }
}
int find(int u){
    if(cut[u]==u)return u;
    return cut[u]=find(cut[u]);
}
void merg(int u,int v){
    int a=find(u),b=find(v);
    if(a==b)return;
    if(h[a]<h[b])cut[b]=a;
    else cut[a]=b;
}
bitset<mxn+10>yes;
int curadd=1;
vector<pii>edge;
int lca(int a,int b){
    if(h[a]<h[b])swap(a,b);
    int k=h[a]-h[b];
    for(int i=0;i<=lg;i++)if(k&(1<<i))a=up[a][i].f;
    if(a==b)return a;
    for(int i=lg;i>=0;i--){
        if(up[a][i].f!=up[b][i].f){
            a=up[a][i].f;
            b=up[b][i].f;
        }
    }
    return up[a][0].f;
}
set<int>s;
void solve(int a,int b){
    a=find(a);
    while(h[a]>h[b]){
        if(a<=1)break;
        merg(a,up[a][0].f);
        if(ans[up[a][0].s]==0)s.insert(up[a][0].s);
        a=find(a);
    }
}
int32_t main(){
    fastio
    cin>>n>>m;
    edge.resize(m+1);
    for(int i=1;i<=m;i++)cin>>edge[i].f>>edge[i].s;
    for(int i=1;i<=n;i++)cut[i]=i;
    for(int i=0;i<n-1;i++){
        int a;cin>>a;
        yes[a]=true;
        adj[edge[a].f].pb({edge[a].s,a});
        adj[edge[a].s].pb({edge[a].f,a});
    }
    dfs(1,-1);
    for(int i=1;i<=lg;i++)for(int j=1;j<=n;j++)up[j][i].f=up[up[j][i-1].f][i-1].f;
    for(int i=1;i<=m;i++){
        if(yes[i]){
            if(ans[i]==0)ans[i]=curadd++;
            continue;
        }
        s.clear();
        int node=lca(edge[i].f,edge[i].s);
        solve(edge[i].f,node);
        solve(edge[i].s,node);
        for(auto j:s)ans[j]=curadd++;
        ans[i]=curadd++;
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
    return 0;
}

Compilation message (stderr)

riggedroads.cpp: In function 'void setIO(std::string)':
riggedroads.cpp:31:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen((name+".out").c_str(),"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