oj.uz

Submission #829237

# Submission time Handle Problem Language Result Execution time Memory
829237 2023-08-18T07:16:45 Z mychecksedad Joker (BOI20_joker) C++17
0 / 100
 116 ms 53340 KB 
/* 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], suf[N];
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});
  }
  Dsu d(n);
  vis.resize(n+1, 0);
  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;
    }
  }
  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] = m + 1;
  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 = max(MX, dp[v][j]);
            v = up[v][j];
          }
        }
        MX = max(MX, dp[v][0]);
      }
      if(u != lca){
        for(int j = K-1; j >= 0; --j){
          if((dep[u]-dep[lca]-1)&(1<<j)){
            MX = max(MX, dp[u][j]);
            u = up[u][j];
          }
        }
        MX = max(MX, dp[u][0]);
      }
      max_time[e[2]] = MX;
    }
  }
  pref[0] = suf[m + 1] = m + 1;
  for(int i = 1; i <= m; ++i) pref[i] = min(pref[i - 1], max_time[i]);
  for(int i = m; i >= 1; --i) suf[i] = min(suf[i + 1], max_time[i]);
  for(;q--;){
    int l, r; cin >> l >> r;
    int MN = min(pref[l - 1], suf[r + 1]);
    if(MN < l){
      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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23780 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Incorrect 11 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23780 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Incorrect 11 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23780 KB Output is correct
3 Incorrect 116 ms 53340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23780 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Incorrect 11 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23780 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Incorrect 11 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23780 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Incorrect 11 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -