oj.uz

Submission #829251

# Submission time Handle Problem Language Result Execution time Memory
829251 2023-08-18T07:39:22 Z mychecksedad Joker (BOI20_joker) C++17
25 / 100
 317 ms 77700 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][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(up[u][j], v)) u = up[u][j];
  return up[u][0];
}
void calc(int r){
  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] = (r == 0 ? max(dp[i][j - 1], dp[up[i][j - 1]][j - 1]) : min(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(r);
    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 = (r == 0 ? 0 : m+1);
        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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 10 ms 23764 KB Output is correct
5 Correct 10 ms 23860 KB Output is correct
6 Correct 10 ms 23828 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Incorrect 11 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 10 ms 23764 KB Output is correct
5 Correct 10 ms 23860 KB Output is correct
6 Correct 10 ms 23828 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Incorrect 11 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 174 ms 55332 KB Output is correct
4 Correct 264 ms 77700 KB Output is correct
5 Correct 251 ms 71824 KB Output is correct
6 Correct 190 ms 56500 KB Output is correct
7 Correct 185 ms 55368 KB Output is correct
8 Correct 145 ms 46660 KB Output is correct
9 Correct 165 ms 54680 KB Output is correct
10 Correct 286 ms 73480 KB Output is correct
11 Correct 157 ms 55060 KB Output is correct
12 Correct 231 ms 70228 KB Output is correct
13 Correct 104 ms 38732 KB Output is correct
14 Correct 152 ms 47160 KB Output is correct
15 Correct 207 ms 62904 KB Output is correct
16 Correct 317 ms 73864 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 10 ms 23764 KB Output is correct
5 Correct 10 ms 23860 KB Output is correct
6 Correct 10 ms 23828 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Incorrect 11 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 10 ms 23764 KB Output is correct
5 Correct 10 ms 23860 KB Output is correct
6 Correct 10 ms 23828 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Incorrect 11 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 10 ms 23764 KB Output is correct
5 Correct 10 ms 23860 KB Output is correct
6 Correct 10 ms 23828 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Incorrect 11 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -