oj.uz

Submission #966828

# Submission time Handle Problem Language Result Execution time Memory
966828 2024-04-20T12:54:36 Z AlperenT_ Swapping Cities (APIO20_swap) C++14
6 / 100
 397 ms 76644 KB 
#include "swap.h"
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ll long long 
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10 + 10,  inf = 1e9+10 , mod = 1e9 + 7 , lg = 20 ;
int cnt = 1 , par[maxn] , dis[maxn] , mark[maxn] , p[maxn][lg+1] , mn[maxn][lg+1]  , mn2[maxn][lg+1] ;
vector <pii> T[maxn] ;
vector <pii> G[maxn];  
set <pii> s[maxn] ;

int find(int v){
  if(par[v]==0)return v;
  return par[v] = find(par[v]) ;
}

void bui(int v , int r =0 ){
  p[v][0] = r;mark[v] = 1;
  rep(i , 1 ,lg)p[v][i] = p[p[v][i-1]][i-1] ; 
  for(auto [w,u] : T[v]){
    if(u == r)continue ;
    bui(u,v);
  }
}

vector<int> tp;
void dfs(int v, int r =0){
  mark[v] =1 ;
  tp.pb(v);
  for(auto [w,u] : T[v]){
    if(r == u)continue ;
    dis[u] = dis[v] + 1;
    mn2[u][0] = w;
    dfs(u , v) ;
    if(sz(s[u]) > sz(s[v]))swap(s[v],s[u]);
    while(sz(s[u])){
      s[v].insert(*s[u].begin());
      s[u].erase(s[u].begin()); 
    }
  }
  for(auto [w,u] : G[v]){
    if(dis[u] < dis[v]){
      s[v].insert({w,u}) ;
    }
  }
  mn[v][0] = inf ;
  while(sz(s[v])){
    int u =(*s[v].begin()).S , w = (*s[v].begin()).F ;
    if(dis[v]<=dis[u]){
      s[v].erase(s[v].begin());
      continue ;
    }
    mn[v][0] = w ;
    break ;
  }
}

pii up(int v ,int d){
    int r = inf , r2 = 0;
    rep(i , 0  ,lg)if(d>>i&1){
      r = min(r , mn[v][i]) ;
      r2= max(r2 , mn2[v][i]) ;
      v = p[v][i] ;
    }
    return (pii){r,r2};
}
int up2(int v ,int d){
     rep(i , 0  ,lg)if(d>>i&1){
      v = p[v][i] ;
    }
    return v; 
}
int lca2(int v, int u){
  if(dis[v] < dis[u])swap(v,u);
  v = up2(v ,dis[v]-dis[u]) ;
  per(i , lg , 0){
    if(p[v][i] != p[u][i]){
      v = p[v][i] ;
      u = p[u][i] ;
    }
  }
  if(v==u)return v ;
  return p[v][0] ;
}
int lca(int v, int u){
  if(dis[v] < dis[u])swap(v,u);
  pii a = up(v , dis[v]-dis[u]) ;
  v = up2(v,dis[v]-dis[u]) ;
  int a1 = a.F ,a2 =a.S; 
  per(i , lg , 0){
    if(p[v][i] != p[u][i]){
      a1 = min({a1 ,mn[v][i] , mn[u][i]});
      a2 = max({a2 ,mn2[v][i] , mn2[u][i]}) ;
      v = p[v][i] ;
      u = p[u][i] ;
    }
  }
  if(v==u)return max(a1 ,a2)  ;
  a1 = min({a1 ,mn[v][0] , mn[u][0]});
  a2 = max({a2 ,mn2[v][0] , mn2[u][0]}) ;
  return max(a1 ,a2);
}
int id[maxn] ;
void init(int n, int m,vector<int>U, vector<int> V, vector<int> W) {
  vector<pair<int,pii> > ed;
  rep(i , 0 , m-1){
    V[i]++;U[i]++;
    ed.pb({W[i] , {V[i],U[i]}});
  }
  sort(all(ed));
  rep(i , 0 ,sz(ed)-1){
    int v = ed[i].S.F, u = ed[i].S.S , w = ed[i].F ;
    if(find(v) == find(u)){
      id[i] = 1 ;
    }else{
      par[find(v)] = find(u);
      T[v].pb({w,u});
      T[u].pb({w,v}); 
    }
  }
  rep(i ,1 , n){
    if(mark[i] == 1)continue ;
    bui(i) ;
  }
  rep(i ,1 ,n)mark[i] =0 ;
  rep(i , 0 , sz(ed)-1){
    if(id[i] == 1){
      int w = ed[i].F , v =ed[i].S.F , u =ed[i].S.S ;
      int lc = lca2(v,u) ;
      G[v].pb({w,lc});
      G[u].pb({w,lc});
    }
  }
  rep(i ,1, n){
    if(mark[i] == 1)continue ;
    dfs(i) ;
  }
  for(int v : tp){
    rep(i , 1 ,lg){
      p[v][i] = p[p[v][i-1]][i-1];
      mn[v][i] = min(mn[v][i-1] , mn[p[v][i-1]][i-1]) ;
      mn2[v][i] = max(mn2[v][i-1] , mn2[p[v][i-1]][i-1]) ;
    }
  }
}

int getMinimumFuelCapacity(int v, int u) {
v++ ;u++;
  if(find(v)!=find(u))return -1 ;
  int ans = lca(v,u);
  if(ans == inf)return -1 ;
  return ans;
}
/* g++ -Wall -lm -static -DEVAL -o swap -O2 swap.cpp grader.cpp -std=c++17 */

Compilation message

swap.cpp: In function 'void bui(int, int)':
swap.cpp:33:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |   for(auto [w,u] : T[v]){
      |            ^
swap.cpp: In function 'void dfs(int, int)':
swap.cpp:43:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |   for(auto [w,u] : T[v]){
      |            ^
swap.cpp:54:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   for(auto [w,u] : G[v]){
      |            ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 24920 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Correct 6 ms 25068 KB Output is correct
4 Correct 6 ms 24924 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25176 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 112 ms 58048 KB Output is correct
10 Correct 163 ms 69552 KB Output is correct
11 Correct 131 ms 68336 KB Output is correct
12 Correct 152 ms 69832 KB Output is correct
13 Correct 132 ms 72784 KB Output is correct
14 Correct 138 ms 57312 KB Output is correct
15 Correct 385 ms 73020 KB Output is correct
16 Correct 361 ms 69828 KB Output is correct
17 Correct 360 ms 76644 KB Output is correct
18 Correct 325 ms 74396 KB Output is correct
19 Correct 84 ms 39688 KB Output is correct
20 Correct 375 ms 71896 KB Output is correct
21 Correct 356 ms 70404 KB Output is correct
22 Correct 397 ms 73496 KB Output is correct
23 Correct 368 ms 74216 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 24920 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Incorrect 189 ms 63940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 24920 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Correct 6 ms 25068 KB Output is correct
4 Correct 6 ms 24924 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25176 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 5 ms 25176 KB Output is correct
10 Incorrect 6 ms 25180 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25176 KB Output is correct
2 Correct 8 ms 24920 KB Output is correct
3 Correct 7 ms 24924 KB Output is correct
4 Correct 6 ms 25068 KB Output is correct
5 Correct 6 ms 24924 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct
7 Correct 6 ms 25176 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 112 ms 58048 KB Output is correct
11 Correct 163 ms 69552 KB Output is correct
12 Correct 131 ms 68336 KB Output is correct
13 Correct 152 ms 69832 KB Output is correct
14 Correct 132 ms 72784 KB Output is correct
15 Incorrect 6 ms 25180 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 24920 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Correct 6 ms 25068 KB Output is correct
4 Correct 6 ms 24924 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25176 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 112 ms 58048 KB Output is correct
10 Correct 163 ms 69552 KB Output is correct
11 Correct 131 ms 68336 KB Output is correct
12 Correct 152 ms 69832 KB Output is correct
13 Correct 132 ms 72784 KB Output is correct
14 Correct 138 ms 57312 KB Output is correct
15 Correct 385 ms 73020 KB Output is correct
16 Correct 361 ms 69828 KB Output is correct
17 Correct 360 ms 76644 KB Output is correct
18 Correct 325 ms 74396 KB Output is correct
19 Incorrect 189 ms 63940 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25176 KB Output is correct
2 Correct 8 ms 24920 KB Output is correct
3 Correct 7 ms 24924 KB Output is correct
4 Correct 6 ms 25068 KB Output is correct
5 Correct 6 ms 24924 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct
7 Correct 6 ms 25176 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 112 ms 58048 KB Output is correct
11 Correct 163 ms 69552 KB Output is correct
12 Correct 131 ms 68336 KB Output is correct
13 Correct 152 ms 69832 KB Output is correct
14 Correct 132 ms 72784 KB Output is correct
15 Correct 138 ms 57312 KB Output is correct
16 Correct 385 ms 73020 KB Output is correct
17 Correct 361 ms 69828 KB Output is correct
18 Correct 360 ms 76644 KB Output is correct
19 Correct 325 ms 74396 KB Output is correct
20 Incorrect 189 ms 63940 KB Output isn't correct
21 Halted 0 ms 0 KB -