oj.uz

Submission #876951

# Submission time Handle Problem Language Result Execution time Memory
876951 2023-11-22T14:55:18 Z 8pete8 Swapping Cities (APIO20_swap) C++14
0 / 100
 313 ms 52724 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 val[a];
  for(int i=lg;i>=0;i--)if((up[a][i]&&up[b][i]&&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 4 ms 13916 KB Output is correct
2 Correct 3 ms 14068 KB Output is correct
3 Correct 3 ms 13896 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 4 ms 13916 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 92 ms 39676 KB Output is correct
10 Correct 99 ms 44996 KB Output is correct
11 Correct 97 ms 44924 KB Output is correct
12 Correct 126 ms 47300 KB Output is correct
13 Correct 108 ms 50540 KB Output is correct
14 Correct 82 ms 39888 KB Output is correct
15 Correct 207 ms 46532 KB Output is correct
16 Correct 215 ms 46464 KB Output is correct
17 Correct 219 ms 48760 KB Output is correct
18 Correct 313 ms 52072 KB Output is correct
19 Correct 73 ms 22356 KB Output is correct
20 Incorrect 200 ms 48680 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13916 KB Output is correct
2 Correct 3 ms 14068 KB Output is correct
3 Correct 3 ms 13896 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 4 ms 13916 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 3 ms 13912 KB Output is correct
10 Correct 4 ms 13916 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 13912 KB Output is correct
2 Correct 4 ms 13916 KB Output is correct
3 Correct 3 ms 14068 KB Output is correct
4 Correct 3 ms 13896 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 3 ms 13916 KB Output is correct
8 Correct 4 ms 13916 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 92 ms 39676 KB Output is correct
11 Correct 99 ms 44996 KB Output is correct
12 Correct 97 ms 44924 KB Output is correct
13 Correct 126 ms 47300 KB Output is correct
14 Correct 108 ms 50540 KB Output is correct
15 Correct 4 ms 13916 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 4 ms 13916 KB Output is correct
2 Correct 3 ms 14068 KB Output is correct
3 Correct 3 ms 13896 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 4 ms 13916 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 92 ms 39676 KB Output is correct
10 Correct 99 ms 44996 KB Output is correct
11 Correct 97 ms 44924 KB Output is correct
12 Correct 126 ms 47300 KB Output is correct
13 Correct 108 ms 50540 KB Output is correct
14 Correct 82 ms 39888 KB Output is correct
15 Correct 207 ms 46532 KB Output is correct
16 Correct 215 ms 46464 KB Output is correct
17 Correct 219 ms 48760 KB Output is correct
18 Correct 313 ms 52072 KB Output is correct
19 Incorrect 242 ms 52724 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 13912 KB Output is correct
2 Correct 4 ms 13916 KB Output is correct
3 Correct 3 ms 14068 KB Output is correct
4 Correct 3 ms 13896 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 3 ms 13916 KB Output is correct
8 Correct 4 ms 13916 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 92 ms 39676 KB Output is correct
11 Correct 99 ms 44996 KB Output is correct
12 Correct 97 ms 44924 KB Output is correct
13 Correct 126 ms 47300 KB Output is correct
14 Correct 108 ms 50540 KB Output is correct
15 Correct 82 ms 39888 KB Output is correct
16 Correct 207 ms 46532 KB Output is correct
17 Correct 215 ms 46464 KB Output is correct
18 Correct 219 ms 48760 KB Output is correct
19 Correct 313 ms 52072 KB Output is correct
20 Incorrect 242 ms 52724 KB Output isn't correct
21 Halted 0 ms 0 KB -