oj.uz

Submission #876950

# Submission time Handle Problem Language Result Execution time Memory
876950 2023-11-22T14:50:40 Z 8pete8 Swapping Cities (APIO20_swap) C++14
0 / 100
 298 ms 52748 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];
bitset<mxn+10>vis;
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){
  if(vis[cur])return;
  vis[cur]=true;
  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;
  for(int i=cnt;i>=0;i--)if(!vis[i])dfs(i);
  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 2 ms 13916 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 13916 KB Output is correct
6 Correct 3 ms 13896 KB Output is correct
7 Correct 3 ms 13940 KB Output is correct
8 Correct 3 ms 13912 KB Output is correct
9 Correct 82 ms 39804 KB Output is correct
10 Correct 97 ms 44916 KB Output is correct
11 Correct 91 ms 44996 KB Output is correct
12 Correct 96 ms 47300 KB Output is correct
13 Correct 100 ms 50536 KB Output is correct
14 Correct 82 ms 39880 KB Output is correct
15 Correct 185 ms 46532 KB Output is correct
16 Correct 188 ms 46372 KB Output is correct
17 Correct 191 ms 48744 KB Output is correct
18 Correct 298 ms 52056 KB Output is correct
19 Correct 71 ms 22452 KB Output is correct
20 Incorrect 207 ms 48700 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13916 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 13916 KB Output is correct
6 Correct 3 ms 13896 KB Output is correct
7 Correct 3 ms 13940 KB Output is correct
8 Correct 3 ms 13912 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 3 ms 13912 KB Output is correct
11 Incorrect 3 ms 13916 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13916 KB Output is correct
2 Correct 2 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 3 ms 13916 KB Output is correct
6 Correct 4 ms 13916 KB Output is correct
7 Correct 3 ms 13896 KB Output is correct
8 Correct 3 ms 13940 KB Output is correct
9 Correct 3 ms 13912 KB Output is correct
10 Correct 82 ms 39804 KB Output is correct
11 Correct 97 ms 44916 KB Output is correct
12 Correct 91 ms 44996 KB Output is correct
13 Correct 96 ms 47300 KB Output is correct
14 Correct 100 ms 50536 KB Output is correct
15 Correct 3 ms 13912 KB Output is correct
16 Incorrect 3 ms 13916 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13916 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 13916 KB Output is correct
6 Correct 3 ms 13896 KB Output is correct
7 Correct 3 ms 13940 KB Output is correct
8 Correct 3 ms 13912 KB Output is correct
9 Correct 82 ms 39804 KB Output is correct
10 Correct 97 ms 44916 KB Output is correct
11 Correct 91 ms 44996 KB Output is correct
12 Correct 96 ms 47300 KB Output is correct
13 Correct 100 ms 50536 KB Output is correct
14 Correct 82 ms 39880 KB Output is correct
15 Correct 185 ms 46532 KB Output is correct
16 Correct 188 ms 46372 KB Output is correct
17 Correct 191 ms 48744 KB Output is correct
18 Correct 298 ms 52056 KB Output is correct
19 Incorrect 224 ms 52748 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13916 KB Output is correct
2 Correct 2 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 3 ms 13916 KB Output is correct
6 Correct 4 ms 13916 KB Output is correct
7 Correct 3 ms 13896 KB Output is correct
8 Correct 3 ms 13940 KB Output is correct
9 Correct 3 ms 13912 KB Output is correct
10 Correct 82 ms 39804 KB Output is correct
11 Correct 97 ms 44916 KB Output is correct
12 Correct 91 ms 44996 KB Output is correct
13 Correct 96 ms 47300 KB Output is correct
14 Correct 100 ms 50536 KB Output is correct
15 Correct 82 ms 39880 KB Output is correct
16 Correct 185 ms 46532 KB Output is correct
17 Correct 188 ms 46372 KB Output is correct
18 Correct 191 ms 48744 KB Output is correct
19 Correct 298 ms 52056 KB Output is correct
20 Incorrect 224 ms 52748 KB Output isn't correct
21 Halted 0 ms 0 KB -