oj.uz

Submission #842178

# Submission time Handle Problem Language Result Execution time Memory
842178 2023-09-02T13:32:30 Z 8pete8 Rigged Roads (NOI19_riggedroads) C++17
30 / 100
 268 ms 117564 KB 
#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(n+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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Runtime error 12 ms 23132 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 21332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 21852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 100328 KB Output is correct
2 Correct 231 ms 112724 KB Output is correct
3 Correct 46 ms 40788 KB Output is correct
4 Correct 64 ms 51800 KB Output is correct
5 Correct 268 ms 117564 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 69940 KB Output is correct
2 Correct 72 ms 51692 KB Output is correct
3 Correct 242 ms 101676 KB Output is correct
4 Correct 221 ms 95728 KB Output is correct
5 Correct 13 ms 19540 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Runtime error 12 ms 23132 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -