| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 733732 | QwertyPi | Misspelling (JOI22_misspelling) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
}