oj.uz

Submission #982645

# Submission time Handle Problem Language Result Execution time Memory
982645 2024-05-14T14:53:13 Z vjudge1 Swapping Cities (APIO20_swap) C++17
13 / 100
 193 ms 46296 KB 
#include "swap.h"
#include <bits/stdc++.h>
 
#pragma optimize("Ofast")
#pragma target("avx2")
 
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert

const int MAX=3e5+15;
const int B=300;
const int N=104;
const int block=400;
const int maxB=MAX/B+10;
const ll inf=2e9;  
const int mod=998244353;
const int mod1=1e9+9;
const ld eps=1e-9;
 
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
 
int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
int mark[MAX];
int cost[MAX];
vector<int> g[MAX];

struct DSU{
  int f[MAX];
  int cur;

  void init(int n,int ver){
    cur=ver;
    for(int i=1;i<=n;i++)f[i]=i;
  }

  int get(int v){
    return f[v]==v?v:f[v]=get(f[v]);
  }

  void unite(int a,int b,bool is,int C){
    a=get(a);
    b=get(b);
    int x=++cur;
    g[x].pb(a);
    g[x].pb(b);
    // cout<<x<<" "<<a<<"\n";
    // cout<<x<<" "<<b<<"\n";
    mark[x]=is;
    cost[x]=C;
    f[a]=f[b]=x;
  }

  void cycle(int a,int C){
    a=get(a);
    int x=++cur;
    cost[x]=C;
    g[x].pb(a);
    // cout<<x<<" "<<a<<"\n";
    mark[x]=1;
    f[a]=x;
  }
}D;

int up[MAX][20];
int tin[MAX],tout[MAX],timer;
int mn[MAX];
int deg[MAX];

void dfs(int v,int p){
  tin[v]=++timer;
  up[v][0]=p;
  // cout<<v<<" "<<p<<"\n";
  for(int i=1;i<20;i++)up[v][i]=up[up[v][i-1]][i-1];
  if(mark[v]){
    mn[v]=cost[v];
  }
  for(auto to:g[v]){
    if(to==p)continue;
    mn[to]=mn[v];
    // cout<<v<<" -> "<<to<<"\n";
    dfs(to,v);
  }
  tout[v]=timer;
}

void dfs1(int v,int p=-1){
  for(auto to:g[v]){
    if(to==p)continue;
    dfs1(to,v);
    mn[v]=min(mn[v],mn[to]);
  }
}

void init(int N, int M,vector<int> U,vector<int> V,vector<int> W) {
  D.init(N+M+M,N);
  vector<pair<int,pii>> e;
  for(int i=0;i<M;i++){
    U[i]++;V[i]++;
    e.pb({W[i],{U[i],V[i]}});
  }
  sort(all(e));
  for(auto x:e){
    int w=x.F;
    int u=x.S.F;
    int v=x.S.S;
    // cerr<<w<<" "<<u<<" "<<v<<"\n";
    if(D.get(u)!=D.get(v)){
      deg[u]++;
      deg[v]++;
      bool is=(deg[u]>=3||deg[v]>=3);
      D.unite(u,v,is,w);
      // if(is)D.cycle(u,w);
    }
    else{
      D.cycle(u,w);
    }
  }
  // cerr<<1<<"\n";
  for(int i=1;i<=D.cur;i++){
    if(!mark[i])mn[i]=inf;
    else mn[i]=cost[i];
  }
  dfs1(D.get(1),D.get(1));
  dfs(D.get(1),D.get(1));
  // for(int i=1;i<=D.cur;i++)cout<<i<<" "<<mn[i]<<" "<<mark[i]<<" "<<cost[i]<<"\n";
}

int par(int a,int b){
  return (tin[a]<=tin[b]&&tout[b]<=tout[a]);
}

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

int getMinimumFuelCapacity(int X, int Y) {
  X++;
  Y++;
  // cout<<lca(X,Y)<<" "<<up[X][19]<<"\n";
  // cout<<cost[lca(X,Y)]<<" "<<mn[X]<<" "<<mn[Y]<<"\n";
  if(max(min(mn[X],mn[Y]),cost[lca(X,Y)])==inf)return -1;
  return max(min(mn[X],mn[Y]),cost[lca(X,Y)]);
}

Compilation message

swap.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    4 | #pragma optimize("Ofast")
      | 
swap.cpp:5: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    5 | #pragma target("avx2")
      |

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14692 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 82 ms 34020 KB Output is correct
10 Correct 99 ms 36548 KB Output is correct
11 Correct 97 ms 36264 KB Output is correct
12 Correct 99 ms 36888 KB Output is correct
13 Correct 86 ms 40644 KB Output is correct
14 Correct 83 ms 32708 KB Output is correct
15 Correct 170 ms 38084 KB Output is correct
16 Correct 181 ms 37800 KB Output is correct
17 Correct 176 ms 38408 KB Output is correct
18 Correct 185 ms 42420 KB Output is correct
19 Correct 68 ms 21588 KB Output is correct
20 Correct 168 ms 38412 KB Output is correct
21 Correct 191 ms 39336 KB Output is correct
22 Correct 193 ms 39856 KB Output is correct
23 Correct 189 ms 43920 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 172 ms 45636 KB Output is correct
4 Correct 178 ms 46212 KB Output is correct
5 Correct 179 ms 46060 KB Output is correct
6 Correct 177 ms 46296 KB Output is correct
7 Correct 184 ms 46276 KB Output is correct
8 Correct 169 ms 45556 KB Output is correct
9 Correct 178 ms 46016 KB Output is correct
10 Correct 167 ms 45368 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14692 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 4 ms 14684 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Correct 3 ms 14936 KB Output is correct
16 Correct 3 ms 14680 KB Output is correct
17 Correct 4 ms 14936 KB Output is correct
18 Correct 4 ms 14940 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Incorrect 3 ms 14828 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14692 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 82 ms 34020 KB Output is correct
11 Correct 99 ms 36548 KB Output is correct
12 Correct 97 ms 36264 KB Output is correct
13 Correct 99 ms 36888 KB Output is correct
14 Correct 86 ms 40644 KB Output is correct
15 Correct 4 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 4 ms 14684 KB Output is correct
20 Correct 3 ms 14936 KB Output is correct
21 Correct 3 ms 14680 KB Output is correct
22 Correct 4 ms 14936 KB Output is correct
23 Correct 4 ms 14940 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Incorrect 3 ms 14828 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14692 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 82 ms 34020 KB Output is correct
10 Correct 99 ms 36548 KB Output is correct
11 Correct 97 ms 36264 KB Output is correct
12 Correct 99 ms 36888 KB Output is correct
13 Correct 86 ms 40644 KB Output is correct
14 Correct 83 ms 32708 KB Output is correct
15 Correct 170 ms 38084 KB Output is correct
16 Correct 181 ms 37800 KB Output is correct
17 Correct 176 ms 38408 KB Output is correct
18 Correct 185 ms 42420 KB Output is correct
19 Correct 172 ms 45636 KB Output is correct
20 Correct 178 ms 46212 KB Output is correct
21 Correct 179 ms 46060 KB Output is correct
22 Correct 177 ms 46296 KB Output is correct
23 Correct 184 ms 46276 KB Output is correct
24 Correct 169 ms 45556 KB Output is correct
25 Correct 178 ms 46016 KB Output is correct
26 Correct 167 ms 45368 KB Output is correct
27 Correct 4 ms 14684 KB Output is correct
28 Correct 3 ms 14684 KB Output is correct
29 Correct 3 ms 14684 KB Output is correct
30 Correct 3 ms 14684 KB Output is correct
31 Correct 4 ms 14684 KB Output is correct
32 Correct 3 ms 14936 KB Output is correct
33 Correct 3 ms 14680 KB Output is correct
34 Correct 4 ms 14936 KB Output is correct
35 Correct 4 ms 14940 KB Output is correct
36 Correct 12 ms 18204 KB Output is correct
37 Correct 111 ms 38496 KB Output is correct
38 Correct 102 ms 39344 KB Output is correct
39 Correct 106 ms 38408 KB Output is correct
40 Correct 101 ms 38344 KB Output is correct
41 Correct 105 ms 38344 KB Output is correct
42 Correct 104 ms 37520 KB Output is correct
43 Correct 105 ms 39620 KB Output is correct
44 Correct 101 ms 38344 KB Output is correct
45 Correct 84 ms 43464 KB Output is correct
46 Correct 107 ms 39876 KB Output is correct
47 Incorrect 18 ms 18564 KB Output isn't correct
48 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14692 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 82 ms 34020 KB Output is correct
11 Correct 99 ms 36548 KB Output is correct
12 Correct 97 ms 36264 KB Output is correct
13 Correct 99 ms 36888 KB Output is correct
14 Correct 86 ms 40644 KB Output is correct
15 Correct 83 ms 32708 KB Output is correct
16 Correct 170 ms 38084 KB Output is correct
17 Correct 181 ms 37800 KB Output is correct
18 Correct 176 ms 38408 KB Output is correct
19 Correct 185 ms 42420 KB Output is correct
20 Correct 172 ms 45636 KB Output is correct
21 Correct 178 ms 46212 KB Output is correct
22 Correct 179 ms 46060 KB Output is correct
23 Correct 177 ms 46296 KB Output is correct
24 Correct 184 ms 46276 KB Output is correct
25 Correct 169 ms 45556 KB Output is correct
26 Correct 178 ms 46016 KB Output is correct
27 Correct 167 ms 45368 KB Output is correct
28 Correct 4 ms 14684 KB Output is correct
29 Correct 3 ms 14684 KB Output is correct
30 Correct 3 ms 14684 KB Output is correct
31 Correct 3 ms 14684 KB Output is correct
32 Correct 4 ms 14684 KB Output is correct
33 Correct 3 ms 14936 KB Output is correct
34 Correct 3 ms 14680 KB Output is correct
35 Correct 4 ms 14936 KB Output is correct
36 Correct 4 ms 14940 KB Output is correct
37 Correct 12 ms 18204 KB Output is correct
38 Correct 111 ms 38496 KB Output is correct
39 Correct 102 ms 39344 KB Output is correct
40 Correct 106 ms 38408 KB Output is correct
41 Correct 101 ms 38344 KB Output is correct
42 Correct 105 ms 38344 KB Output is correct
43 Correct 104 ms 37520 KB Output is correct
44 Correct 105 ms 39620 KB Output is correct
45 Correct 101 ms 38344 KB Output is correct
46 Correct 84 ms 43464 KB Output is correct
47 Correct 107 ms 39876 KB Output is correct
48 Incorrect 18 ms 18564 KB Output isn't correct
49 Halted 0 ms 0 KB -