oj.uz

Submission #675929

# Submission time Handle Problem Language Result Execution time Memory
675929 2022-12-28T12:02:12 Z Sam_a17 Swapping Cities (APIO20_swap) C++17
23 / 100
 2000 ms 46148 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int)x.size()
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount
 
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for random generations
// mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
mt19937 myrand(373);
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if(str == "input") {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  } else {
    // freopen("skis.in", "r", stdin);
    // freopen("skis.out", "w", stdout);
  }
}
// Indexed Set  
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 5e5 + 10, LOG = 22;
int a[N], n, mx, m, sz[N], p[N], deg[N], mx_edge[N], new_node;
vector<int> adj[N];
int up[N][LOG], in[N], depths[N];
bool exist[N];
set<pair<int, int>> st;
bool flag1 = true;

// dsu
int find(int a) {
  // dbg(a)
  if(a != p[a]) {
    return find(p[a]);
  }
  return p[a];
}

int same(int a, int b) {
  if(find(a) == find(b)) {
    return 1;
  }
  return 0;
}

int merge(int a, int b, int curr) {
  deg[a]++, deg[b]++;
  bool is_possible = false;
  if(deg[a] >= 3 || deg[b] >= 3) is_possible = true; 
  a = find(a), b = find(b);
  if(a == b) {
    if(!exist[a]) {
      mx_edge[a] = curr;
      exist[a] = true;
    }
    return 0;
  }

  if(sz[b] > sz[a]) {
    swap(a, b);
  }

  sz[new_node] = sz[a] + sz[b];
  p[b] = new_node, p[a] = new_node;
  
  //
  adj[new_node].push_back(a);
  adj[new_node].push_back(b);
  in[a]++, in[b]++;

  up[b][0] = new_node, up[a][0] = new_node;
  mx_edge[new_node] = curr;
  exist[new_node] = (exist[a] || exist[b] || is_possible);

  new_node++;
  return 1;
}

void dfs(int node, int parent) {
  depths[node] = depths[parent] + 1;
  for(auto i: adj[node]) {
    dfs(i, node);
  }
}

int lca(int a, int b) {
  if(a == b) {
    return a;
  }

  if(depths[a] > depths[b]) {
    swap(a, b);
  }

  int delta = depths[b] - depths[a];
  for(int i = 0; i < LOG; i++) {
    if(delta & (1 << i)) {
      b = up[b][i];
    }
  }

  if(a == b) {
    return a;
  }

  for(int i = LOG - 1; i >= 0; i--) {
    if(up[a][i] != up[b][i]) {
      a = up[a][i], b = up[b][i];
    }
  }
  return up[a][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  n = N, m = M;
  vector<pair<int, pair<int, int>>> edges;
  for(int i = 0; i < M; i++) {
    U[i]++, V[i]++;
    edges.push_back({W[i], {U[i], V[i]}});
  }

  new_node = n + 1;
  sort(all(edges));

  for(int i = 0; i < ::N; i++) {
    p[i] = i, sz[i] = 1;
  }

  for(int i = 0; i < M; i++) {
    merge(edges[i].second.first, edges[i].second.second, edges[i].first);
  }

  for(int i = 1; i < LOG; i++) {
    for(int j = 1; j < new_node; j++) {
      up[j][i] = up[up[j][i - 1]][i - 1];
    }
  }

  for(int i = 1; i < new_node; i++) {
    if(!in[i]) {
      dfs(i, 0);
    }
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  X++,Y++;

  int lc = lca(X, Y);
  int ina = 0, inb = N - 10, answ = -1;
  while(ina <= inb) {
    int mid = (ina + inb) / 2;
    int curr = lc;
    for(int i = 0; i < LOG; i++) {
      if(mid & (1 << i)) {
        curr = up[curr][i];  
      } 
    }

    if(!curr) {
      inb = mid - 1;
      continue;
    }

    if(exist[curr]) {
      answ = mid;
      inb = mid - 1;
    } else {
      ina = mid + 1;
    }
  }
  
  if(answ == -1) {
    return answ;
  }

  int curr = lc;
  for(int i = 0; i < LOG; i++) {
    if(answ & (1 << i)) {
      curr = up[curr][i];  
    } 
  }
  return mx_edge[curr];
}

Compilation message

swap.cpp: In function 'void setIO(std::string)':
swap.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 9 ms 15936 KB Output is correct
3 Correct 8 ms 15956 KB Output is correct
4 Correct 9 ms 16084 KB Output is correct
5 Correct 9 ms 16212 KB Output is correct
6 Correct 8 ms 16212 KB Output is correct
7 Correct 9 ms 16212 KB Output is correct
8 Correct 9 ms 16292 KB Output is correct
9 Correct 94 ms 36780 KB Output is correct
10 Correct 113 ms 41204 KB Output is correct
11 Correct 112 ms 40764 KB Output is correct
12 Correct 149 ms 42332 KB Output is correct
13 Correct 161 ms 43676 KB Output is correct
14 Correct 138 ms 36652 KB Output is correct
15 Correct 390 ms 42944 KB Output is correct
16 Correct 437 ms 42228 KB Output is correct
17 Correct 411 ms 43828 KB Output is correct
18 Correct 858 ms 45184 KB Output is correct
19 Correct 209 ms 23968 KB Output is correct
20 Correct 476 ms 43904 KB Output is correct
21 Correct 435 ms 43184 KB Output is correct
22 Correct 463 ms 44848 KB Output is correct
23 Correct 772 ms 46148 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 9 ms 15936 KB Output is correct
3 Execution timed out 2068 ms 35104 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 9 ms 15936 KB Output is correct
3 Correct 8 ms 15956 KB Output is correct
4 Correct 9 ms 16084 KB Output is correct
5 Correct 9 ms 16212 KB Output is correct
6 Correct 8 ms 16212 KB Output is correct
7 Correct 9 ms 16212 KB Output is correct
8 Correct 9 ms 16292 KB Output is correct
9 Correct 9 ms 15956 KB Output is correct
10 Correct 9 ms 16256 KB Output is correct
11 Correct 9 ms 16188 KB Output is correct
12 Correct 10 ms 16256 KB Output is correct
13 Correct 9 ms 16156 KB Output is correct
14 Correct 9 ms 16124 KB Output is correct
15 Correct 9 ms 16212 KB Output is correct
16 Correct 13 ms 16280 KB Output is correct
17 Correct 11 ms 16212 KB Output is correct
18 Correct 13 ms 16284 KB Output is correct
19 Correct 10 ms 16212 KB Output is correct
20 Correct 10 ms 16212 KB Output is correct
21 Correct 9 ms 16200 KB Output is correct
22 Correct 12 ms 16136 KB Output is correct
23 Correct 11 ms 16136 KB Output is correct
24 Correct 10 ms 16212 KB Output is correct
25 Correct 12 ms 16212 KB Output is correct
26 Correct 13 ms 16212 KB Output is correct
27 Correct 10 ms 16172 KB Output is correct
28 Correct 12 ms 16236 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 9 ms 15936 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 9 ms 16084 KB Output is correct
6 Correct 9 ms 16212 KB Output is correct
7 Correct 8 ms 16212 KB Output is correct
8 Correct 9 ms 16212 KB Output is correct
9 Correct 9 ms 16292 KB Output is correct
10 Correct 94 ms 36780 KB Output is correct
11 Correct 113 ms 41204 KB Output is correct
12 Correct 112 ms 40764 KB Output is correct
13 Correct 149 ms 42332 KB Output is correct
14 Correct 161 ms 43676 KB Output is correct
15 Correct 9 ms 16256 KB Output is correct
16 Correct 9 ms 16188 KB Output is correct
17 Correct 10 ms 16256 KB Output is correct
18 Correct 9 ms 16156 KB Output is correct
19 Correct 9 ms 16124 KB Output is correct
20 Correct 9 ms 16212 KB Output is correct
21 Correct 13 ms 16280 KB Output is correct
22 Correct 11 ms 16212 KB Output is correct
23 Correct 13 ms 16284 KB Output is correct
24 Correct 10 ms 16212 KB Output is correct
25 Correct 10 ms 16212 KB Output is correct
26 Correct 9 ms 16200 KB Output is correct
27 Correct 12 ms 16136 KB Output is correct
28 Correct 11 ms 16136 KB Output is correct
29 Correct 10 ms 16212 KB Output is correct
30 Correct 12 ms 16212 KB Output is correct
31 Correct 13 ms 16212 KB Output is correct
32 Correct 10 ms 16172 KB Output is correct
33 Correct 12 ms 16236 KB Output is correct
34 Correct 20 ms 19476 KB Output is correct
35 Correct 141 ms 42272 KB Output is correct
36 Correct 133 ms 42320 KB Output is correct
37 Correct 124 ms 42292 KB Output is correct
38 Correct 120 ms 41960 KB Output is correct
39 Correct 137 ms 41736 KB Output is correct
40 Correct 140 ms 39608 KB Output is correct
41 Correct 126 ms 42408 KB Output is correct
42 Correct 129 ms 42248 KB Output is correct
43 Correct 151 ms 43996 KB Output is correct
44 Correct 133 ms 42284 KB Output is correct
45 Execution timed out 2066 ms 38040 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 9 ms 15936 KB Output is correct
3 Correct 8 ms 15956 KB Output is correct
4 Correct 9 ms 16084 KB Output is correct
5 Correct 9 ms 16212 KB Output is correct
6 Correct 8 ms 16212 KB Output is correct
7 Correct 9 ms 16212 KB Output is correct
8 Correct 9 ms 16292 KB Output is correct
9 Correct 94 ms 36780 KB Output is correct
10 Correct 113 ms 41204 KB Output is correct
11 Correct 112 ms 40764 KB Output is correct
12 Correct 149 ms 42332 KB Output is correct
13 Correct 161 ms 43676 KB Output is correct
14 Correct 138 ms 36652 KB Output is correct
15 Correct 390 ms 42944 KB Output is correct
16 Correct 437 ms 42228 KB Output is correct
17 Correct 411 ms 43828 KB Output is correct
18 Correct 858 ms 45184 KB Output is correct
19 Execution timed out 2068 ms 35104 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 9 ms 15936 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 9 ms 16084 KB Output is correct
6 Correct 9 ms 16212 KB Output is correct
7 Correct 8 ms 16212 KB Output is correct
8 Correct 9 ms 16212 KB Output is correct
9 Correct 9 ms 16292 KB Output is correct
10 Correct 94 ms 36780 KB Output is correct
11 Correct 113 ms 41204 KB Output is correct
12 Correct 112 ms 40764 KB Output is correct
13 Correct 149 ms 42332 KB Output is correct
14 Correct 161 ms 43676 KB Output is correct
15 Correct 138 ms 36652 KB Output is correct
16 Correct 390 ms 42944 KB Output is correct
17 Correct 437 ms 42228 KB Output is correct
18 Correct 411 ms 43828 KB Output is correct
19 Correct 858 ms 45184 KB Output is correct
20 Execution timed out 2068 ms 35104 KB Time limit exceeded
21 Halted 0 ms 0 KB -