Submission #733732

#	Time	Username	Problem	Language	Result	Execution time	Memory
733732		QwertyPi	Misspelling (JOI22_misspelling)	C++14	Compilation error	0 ms	0 KiB

misspelling

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N_MAX = 5e5 + 11;
const int MOD = 1e9 + 7;
const int INF = 1LL << 60;

vector<int> G[N_MAX], Gi[N_MAX];
vector<int> tp;
bool vis[N_MAX];
vector<int> scc[N_MAX];

struct Edge{
	int u, v;
};

void dfs(int u, int pa = -1){
	vis[u] = true;
	for(auto v : G[u]){
		if(!vis[v]){
			dfs(v, u);
		}
	}
	tp.push_back(u);
}

int n, m;

int imax[N_MAX], imin[N_MAX], omax[N_MAX], omin[N_MAX];

void dfs_dp1(int u, int pa = -1){
	vis[u] = true; omax[u] = omin[u] = u;
	for(auto v : G[u]){
		if(!vis[v]){
			dfs_dp1(v, u);
		}
		omax[u] = max(omax[u], omax[v]);
		omin[u] = min(omin[u], omin[v]);
	}
}

void dfs_dp2(int u, int pa = -1){
	vis[u] = true; imax[u] = imin[u] = u;
	for(auto v : Gi[u]){
		if(!vis[v]){
			dfs_dp2(v, u);
		}
		imax[u] = max(imax[u], imax[v]);
		imin[u] = min(imin[u], imin[v]);
	}
}

void dp_combine(){
	fill(imax, imax + n, -INF);
	fill(imin, imin + n, INF);
	fill(omax, omax + n, -INF);
	fill(omin, omin + n, INF);
	
	fill(vis, vis + n, 0);
	for(int i = 0; i < n; i++){
		if(!vis[i]) dfs_dp1(i);
	}
	
	fill(vis, vis + n, 0);
	for(int i = 0; i < n; i++){
		if(!vis[i]) dfs_dp2(i);
	}
}

struct DSU{
	int dsu[N_MAX], l[N_MAX], r[N_MAX];
	void init(int n){
		for(int i = 0; i < n; i++){
			dsu[i] = l[i] = r[i] = i;
		}
	}
	int root(int x){
		return x == dsu[x] ? x : dsu[x] = root(dsu[x]);
	}
	void join(int x, int y){
		x = root(x), y = root(y);
		if(x > y) swap(x, y);
		if(x != y) {
			dsu[x] = y;
			l[y] = x;
			r[y] = y;
		}
	}
	void join_range(int l, int r){
		l = root(l), r = root(r);
		while(l < r){
			join(l, l + 1);
			l = root(l);
		}
	}
} dsu;

int dp_calc(){
	vector<int> v;
	for(int i = 0; i < n; i++){
		if(dsu.root(i) == i){
			v.push_back(i);
		}
	}
	return ans;
}

void rdfs(int id, int u, int pa = -1){
	vis[u] = true; scc[id].push_back(u);
	for(auto v : Gi[u]){
		if(!vis[v]){
			rdfs(id, v, u);
		}
	}
}

vector<Edge> E;
void rebuild(){
	for(int i = 0; i < n; i++){
		G[i].clear(); Gi[i].clear();
	}
	for(int i = 0; i < m; i++){
		int u = dsu.root(E[i].u), v = dsu.root(E[i].v);
		if(u == v) continue;
		G[u].push_back(v); Gi[v].push_back(u);
	}
}

int32_t main(){
	cin >> n >> m; dsu.init(n);
	for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b; a--; b--;
		G[a].push_back(b); 
		Gi[b].push_back(a);
		E.push_back({a, b});
	}
	for(int i = 0; i < n; i++){
		if(!vis[i]) dfs(i);
	}
	fill(vis, vis + n, 0); int sid = 0;
	for(int i = n - 1; i >= 0; i--){
		if(!vis[tp[i]]) rdfs(sid++, tp[i]);
	}
	for(int i = 0; i < sid; i++){
		for(int j = 0; j < (int) scc[i].size() - 1; j++){
			dsu.join_range(scc[i][j], scc[i][j + 1]);
		}
	}

	rebuild();
	dp_combine();
	for(int i = 0; i < n; i++){
		dsu.join_range(i, min(imax[i], omax[i]));
	}
	rebuild();
	int ans = dp_calc();
	cout << ans << endl;
	/*
	for(int i = 0; i < n; i++){
		cout << omin[i] << ' ';
	}
	cout << endl;
	for(int i = 0; i < n; i++){
		cout << omax[i] << ' ';
	}
	cout << endl;
	for(int i = 0; i < n; i++){
		cout << imin[i] << ' ';
	}
	cout << endl;
	for(int i = 0; i < n; i++){
		cout << imax[i] << ' ';
	}
	cout << endl;
	*/
	for(int i = 0; i < n; i++){
		cout << dsu.root(i) << ' ';
	}
	cout << endl;
	for(int i = 0; i < n; i++){
		cout << "G[" << i << "] => ";
		for(auto j : G[i]){
			cout << j << ' ';
		}
		cout << endl;
	} 
}

Compilation message (stderr)

misspelling.cpp: In function 'long long int dp_calc()':
misspelling.cpp:106:9: error: 'ans' was not declared in this scope; did you mean 'abs'?
  106 |  return ans;
      |         ^~~
      |         abs