Submission #829246

#	Time	Username	Problem	Language	Result	Execution time	Memory
829246		mychecksedad	Joker (BOI20_joker)	C++17	0 / 100	173 ms	55176 KiB

Joker

/* Author : Tr3nity  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod1 (1000000000+7)
#define mod (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18;



struct Dsu {
  vector<int> s, p;
  int sz;
  Dsu(int n){
    sz = n;
    s.resize(n+1, 1);
    p.resize(n+1);
    for(int i = 0; i <= n; ++i) p[i] = i;
  }
  int find(int v){
    if(p[v] == v) return v;
    return (p[v] = find(p[v]));
  }
  void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a != b){
      if(s[a] > s[b]){
        swap(a, b);
      }
      s[b] += s[a];
      p[a] = b;
      sz--;
    }
  }
};


int n, m, q, tin[N], tout[N], timer = 0, up[N][K], dp[N][K], dep[N], max_time[N], pref[N][2], suf[N][2];
vector<array<int, 3>> edges;
vector<pair<int, int>> g[N];
vector<bool> vis, in_mst;

void dfs(int v){
  vis[v] = 1;
  tin[v] = timer++;
  for(auto e: g[v]){
    int u = e.first, t = e.second;
    if(!vis[u]){
      dep[u] = dep[v] + 1;
      dfs(u);
      dp[u][0] = t;
      up[u][0] = v;
    }
  }
  tout[v] = timer++;
}

bool is_ancestor(int u, int v){
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int _lca(int u, int v){
  if(is_ancestor(u, v)) return u;
  if(is_ancestor(v, u)) return v;
  for(int j = K-1; j >= 0; --j)
    if(!is_ancestor(dp[u][j], v)) u = dp[u][j];
  return dp[u][0];
}
void calc(){
  for(int j = 1; j < K; ++j)
    for(int i = 1; i <= n; ++i){
      up[i][j] = up[up[i][j - 1]][j - 1];
      dp[i][j] = max(dp[i][j - 1], dp[up[i][j - 1]][j - 1]);
    }
}

void solve(){
  cin >> n >> m >> q;
  for(int i = 0; i < m; ++i){
    int u, v; cin >> u >> v;
    edges.pb({u, v, i + 1});
  }
  for(int r = 0; r < 2; ++r){
    for(int i = 1; i <= n; ++i) g[i].clear();
    Dsu d(n);
    vis.clear();
    vis.resize(n+1, 0);
    in_mst.clear();
    in_mst.resize(m+1, 0);
    for(auto e: edges){
      if(d.find(e[0]) != d.find(e[1])){
        g[e[0]].pb({e[1], e[2]});
        g[e[1]].pb({e[0], e[2]});
        d.merge(e[0], e[1]);
        in_mst[e[2]] = 1;
      }
    }
    timer = 0;
    for(int i = 1; i <= n; ++i){
      if(!vis[i]){
        dep[i] = 0;
        up[i][0] = i;
        dp[i][0] = 0;
        dfs(i);
      }
    }
    calc();
    for(int i = 1; i <= m; ++i) max_time[i] = (r == 0 ? m + 1 : 0);
    for(auto e: edges){
      if(!in_mst[e[2]]){
        int u = e[0], v = e[1];
        if(dep[u] % 2 != dep[v] % 2) continue;
        int lca = _lca(u, v), MX = 0;
        if(v != lca){
          for(int j = K-1; j >= 0; --j){
            if((dep[v]-dep[lca]-1)&(1<<j)){
              MX = (r == 0 ? max(MX, dp[v][j]) : min(MX, dp[v][j]));
              v = up[v][j];
            }
          }
          MX = (r == 0 ? max(MX, dp[v][0]) : min(MX, dp[v][0]));
        }
        if(u != lca){
          for(int j = K-1; j >= 0; --j){
            if((dep[u]-dep[lca]-1)&(1<<j)){
              MX = (r == 0 ? max(MX, dp[u][j]) : min(MX, dp[u][j]));
              u = up[u][j];
            }
          }
          MX = (r == 0 ? max(MX, dp[u][0]) : min(MX, dp[u][0]));
        }
        max_time[e[2]] = MX;
      }
    }
    pref[0][r] = suf[m + 1][r] = (r == 0 ? m + 1 : 0);
    for(int i = 1; i <= m; ++i) pref[i][r] = (r == 0 ? 
      min(pref[i - 1][r], max_time[i]) : 
      max(pref[i - 1][r], max_time[i]));
    for(int i = m; i >= 1; --i) suf[i][r] = (r == 0 ? 
      min(suf[i + 1][r], max_time[i]) : 
      max(suf[i + 1][r], max_time[i]));

    reverse(all(edges));
  }
  for(;q--;){
    int l, r; cin >> l >> r;
    int MN = min(pref[l - 1][0], suf[r + 1][0]);
    int MX = max(pref[l - 1][1], suf[r + 1][1]);
    if(MN < l || MX > r){
      cout << "YES\n";
    }else cout << "NO\n";
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;aa=tt;
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:161:15: warning: unused variable 'aa' [-Wunused-variable]
  161 |   int tt = 1, aa;
      |               ^~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29