oj.uz

Submission #876947

# Submission time Handle Problem Language Result Execution time Memory
876947 2023-11-22T14:46:17 Z 8pete8 Swapping Cities (APIO20_swap) C++14
0 / 100
 294 ms 54728 KB 
#include "swap.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include <iomanip>  
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define ll long long    
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
const int mxn=3e5,lg=30;
int pa[mxn+10],deg[mxn+10],val[mxn+10],up[mxn+10][lg+5],h[mxn+10];
bool yes[mxn+10];
vector<int>adj[mxn+10];
int find(int u){return ((pa[u]==u)?u:pa[u]=find(pa[u]));}
int cnt=0;
void merg(int a,int b){
  int u=find(a),v=find(b);
  cnt++;
  if(u==v){
    yes[cnt]=true;
    adj[cnt].pb(v);
    pa[v]=cnt;
    return;
  }
  adj[cnt].pb(v);
  adj[cnt].pb(u);
  yes[cnt]=(yes[v]|yes[u]);
  deg[a]++,deg[b]++;
  if(deg[a]>=3||deg[b]>=3)yes[cnt]=true;
  pa[u]=pa[v]=cnt;
}
void dfs(int cur){for(auto i:adj[cur])h[i]=h[cur]+1,up[i][0]=cur,dfs(i);}
void init(int n,int m,vector<int>u,vector<int>v,vector<int>w){
  cnt=n-1;
  for(int i=0;i<mxn;i++)pa[i]=i;
  vector<ppii>e;
  for(int i=0;i<m;i++)e.pb({w[i],{u[i],v[i]}});
  sort(all(e));
  for(auto i:e)merg(i.s.f,i.s.s),val[cnt]=i.f;
  dfs(cnt);
  for(int j=1;j<=lg;j++)for(int i=0;i<=cnt;i++)up[i][j]=up[up[i][j-1]][j-1];
}
int getMinimumFuelCapacity(int a,int b){
  if(h[a]<h[b])swap(a,b);
  int k=h[a]-h[b];
  for(int i=0;i<=lg;i++)if(k&(1<<i))a=up[a][i];
  if(a==b&&yes[a])return a;
  for(int i=lg;i>=0;i--){
    if(up[a][i]!=up[b][i]||(up[a][i]&&up[a][i]==up[b][i]&&!yes[up[a][i]])){
      a=up[a][i];
      b=up[b][i];
    }
  }
  if(up[a][0]==up[b][0]&&(yes[up[a][0]]))return val[up[a][0]];
  return -1;
}/*
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));
  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);
  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }
  
  return 0;
}*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13912 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 4 ms 14180 KB Output is correct
7 Correct 3 ms 14172 KB Output is correct
8 Correct 4 ms 13968 KB Output is correct
9 Correct 81 ms 41416 KB Output is correct
10 Correct 101 ms 47048 KB Output is correct
11 Correct 107 ms 46792 KB Output is correct
12 Correct 103 ms 49352 KB Output is correct
13 Correct 102 ms 50888 KB Output is correct
14 Correct 86 ms 41812 KB Output is correct
15 Correct 195 ms 51060 KB Output is correct
16 Correct 197 ms 50628 KB Output is correct
17 Correct 197 ms 53188 KB Output is correct
18 Correct 294 ms 54728 KB Output is correct
19 Correct 71 ms 24408 KB Output is correct
20 Incorrect 197 ms 52900 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13912 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Incorrect 227 ms 53512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13912 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 4 ms 14180 KB Output is correct
7 Correct 3 ms 14172 KB Output is correct
8 Correct 4 ms 13968 KB Output is correct
9 Correct 4 ms 13916 KB Output is correct
10 Correct 3 ms 14180 KB Output is correct
11 Incorrect 3 ms 14424 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13916 KB Output is correct
2 Correct 3 ms 13912 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 4 ms 14172 KB Output is correct
7 Correct 4 ms 14180 KB Output is correct
8 Correct 3 ms 14172 KB Output is correct
9 Correct 4 ms 13968 KB Output is correct
10 Correct 81 ms 41416 KB Output is correct
11 Correct 101 ms 47048 KB Output is correct
12 Correct 107 ms 46792 KB Output is correct
13 Correct 103 ms 49352 KB Output is correct
14 Correct 102 ms 50888 KB Output is correct
15 Correct 3 ms 14180 KB Output is correct
16 Incorrect 3 ms 14424 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13912 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 4 ms 14180 KB Output is correct
7 Correct 3 ms 14172 KB Output is correct
8 Correct 4 ms 13968 KB Output is correct
9 Correct 81 ms 41416 KB Output is correct
10 Correct 101 ms 47048 KB Output is correct
11 Correct 107 ms 46792 KB Output is correct
12 Correct 103 ms 49352 KB Output is correct
13 Correct 102 ms 50888 KB Output is correct
14 Correct 86 ms 41812 KB Output is correct
15 Correct 195 ms 51060 KB Output is correct
16 Correct 197 ms 50628 KB Output is correct
17 Correct 197 ms 53188 KB Output is correct
18 Correct 294 ms 54728 KB Output is correct
19 Incorrect 227 ms 53512 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13916 KB Output is correct
2 Correct 3 ms 13912 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 4 ms 14172 KB Output is correct
7 Correct 4 ms 14180 KB Output is correct
8 Correct 3 ms 14172 KB Output is correct
9 Correct 4 ms 13968 KB Output is correct
10 Correct 81 ms 41416 KB Output is correct
11 Correct 101 ms 47048 KB Output is correct
12 Correct 107 ms 46792 KB Output is correct
13 Correct 103 ms 49352 KB Output is correct
14 Correct 102 ms 50888 KB Output is correct
15 Correct 86 ms 41812 KB Output is correct
16 Correct 195 ms 51060 KB Output is correct
17 Correct 197 ms 50628 KB Output is correct
18 Correct 197 ms 53188 KB Output is correct
19 Correct 294 ms 54728 KB Output is correct
20 Incorrect 227 ms 53512 KB Output isn't correct
21 Halted 0 ms 0 KB -