Submission #600028

#	Time	Username	Problem	Language	Result	Execution time	Memory
600028		TimDee	Event Hopping (BOI22_events)	C++17	0 / 100	252 ms	89840 KiB

events

//#pragma GCC optimize("O1")
//#pragma GCC optimize("O2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define forn(i,n) for (int i=0; i<n; ++i)
#define pb(x) push_back(x);
#define f first
#define s second

struct DSU {
 
    vector<int> p;
    vector<int> r;
    
    DSU(int n) {
        p.assign(n,0);
        r.assign(n,0);
        forn(i,n) p[i]=i;
    }
    
    int get(int i) {
           
        return p[i]==i ? i : get(p[i]);
        
    }
    
    void uni(int a, int b) {
        
        a=get(a);
        b=get(b);
        if (a==b) return;
        
        if (r[a]==r[b]) r[a]++;
        
        if (r[a]>r[b]) {
            p[b]=a;
        } else {
            p[a]=b;
        }
        
    }
    
};

void dfs(vector<vector<int>>&adj, int u, vector<int>&d) {
	for (auto v:adj[u]) {
		d[v]=d[u]+1;
		dfs(adj,v,d);
	}
}

void solve() {
	int n, m; cin>>n>>m;
	vector<pair<int,int>> a(n);
	vector<vector<int>> adj(n), rev(n);
	DSU paiu(n);
	map<int,int> was;
	map<int,int> ind;
	forn(i,n) {
		int l,r; cin>>l>>r;
		if (was[r]) {
			paiu.uni(ind[r],i);
			if (l<was[r]) {
				was[r]=l;
				ind[r]=i;
			}
		} else {
			was[r]=l;
			ind[r]=i;
		}
	}

	set<pair<int,int>> s;
	vector<int> in(n,0);
	for (auto x:was) s.insert({x.f,ind[x.f]});
	auto p = s.end(); --p;
	for (;;--p) {
		auto x=*p; int i=x.s;
		auto it = s.upper_bound({was[x.f],-1});
		auto z=*it; if (z.f<was[x.f]) ++it;
		while (it!=s.end() && (*it).f<=x.f) {
			if ((*it).s!=i) { adj[(*it).s].pb(i); in[i]++; rev[i].pb((*it).s); }
			++it;
		}
		if (p==s.begin()) break;
	}

	vector<vector<int>> jump(n,vector<int>(32,0));
	vector<int> depth(n,0);
	queue<int> q;
	for (auto it:ind) if (in[it.s]==0) q.push(it.s); int root;
	while (!q.empty()) {
		int u=q.front(); q.pop();
		if (adj[u].size()) {
			jump[u][0]=adj[u][0];
		} else {
			jump[u][0]=u; root=u;
		}
	}

	dfs(rev,root,depth);

	for (int j=1; j<32; ++j) {
		forn(i,n) {
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}

	forn(i,m) {
		int u,v; cin>>u>>v;
		--u,--v;
		if (u==v) cout<<"0\n";
		else if (depth[v]>depth[u]) cout<<"impossible\n";
		else {
			int ans=0;
			for (int i=31; i>=0; --i) {
				if (depth[jump[u][i]]<=depth[v]) continue;
				cout<<u<<"->"<<jump[u][i]<<" 2^"<<i<<'\n';
				u=jump[u][i]; 
				ans+=(1<<i);
			}
			if (jump[u][0]==v) cout<<ans+1<<'\n';
			else cout<<"impossible\n";
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

Compilation message (stderr)

events.cpp: In function 'void solve()':
events.cpp:97:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   97 |  for (auto it:ind) if (in[it.s]==0) q.push(it.s); int root;
      |  ^~~
events.cpp:97:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   97 |  for (auto it:ind) if (in[it.s]==0) q.push(it.s); int root;
      |                                                   ^~~
events.cpp:107:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |  dfs(rev,root,depth);
      |  ~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30