oj.uz

Submission #982642

# Submission time Handle Problem Language Result Execution time Memory
982642 2024-05-14T14:39:23 Z shenfe1 Swapping Cities (APIO20_swap) C++17
6 / 100
 188 ms 43716 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]=min(mn[v],cost[v]);
  }
  for(auto to:g[v]){
    if(to==p)continue;
    mn[to]=min(mn[to],mn[v]);
    // cout<<v<<" -> "<<to<<"\n";
    dfs(to,v);
  }
  tout[v]=timer;
}

void init(int N, int M,vector<int> U,vector<int> V,vector<int> W) {
  D.init(N+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);
    }
    else{
      D.cycle(u,w);
    }
  }
  // cerr<<1<<"\n";
  for(int i=1;i<=D.cur;i++)mn[i]=inf;
  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 2 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 3 ms 14840 KB Output is correct
5 Correct 3 ms 14680 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 73 ms 34000 KB Output is correct
10 Correct 94 ms 36552 KB Output is correct
11 Correct 91 ms 36292 KB Output is correct
12 Correct 96 ms 36816 KB Output is correct
13 Correct 79 ms 39876 KB Output is correct
14 Correct 83 ms 32716 KB Output is correct
15 Correct 158 ms 38084 KB Output is correct
16 Correct 158 ms 37824 KB Output is correct
17 Correct 164 ms 38340 KB Output is correct
18 Correct 188 ms 41564 KB Output is correct
19 Correct 66 ms 21592 KB Output is correct
20 Correct 169 ms 38440 KB Output is correct
21 Correct 165 ms 39440 KB Output is correct
22 Correct 167 ms 39828 KB Output is correct
23 Correct 177 ms 42924 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Incorrect 166 ms 43716 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 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 3 ms 14840 KB Output is correct
5 Correct 3 ms 14680 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 2 ms 14680 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Incorrect 3 ms 14684 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14840 KB Output is correct
6 Correct 3 ms 14680 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 73 ms 34000 KB Output is correct
11 Correct 94 ms 36552 KB Output is correct
12 Correct 91 ms 36292 KB Output is correct
13 Correct 96 ms 36816 KB Output is correct
14 Correct 79 ms 39876 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Incorrect 3 ms 14684 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 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 3 ms 14840 KB Output is correct
5 Correct 3 ms 14680 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 73 ms 34000 KB Output is correct
10 Correct 94 ms 36552 KB Output is correct
11 Correct 91 ms 36292 KB Output is correct
12 Correct 96 ms 36816 KB Output is correct
13 Correct 79 ms 39876 KB Output is correct
14 Correct 83 ms 32716 KB Output is correct
15 Correct 158 ms 38084 KB Output is correct
16 Correct 158 ms 37824 KB Output is correct
17 Correct 164 ms 38340 KB Output is correct
18 Correct 188 ms 41564 KB Output is correct
19 Incorrect 166 ms 43716 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14840 KB Output is correct
6 Correct 3 ms 14680 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 73 ms 34000 KB Output is correct
11 Correct 94 ms 36552 KB Output is correct
12 Correct 91 ms 36292 KB Output is correct
13 Correct 96 ms 36816 KB Output is correct
14 Correct 79 ms 39876 KB Output is correct
15 Correct 83 ms 32716 KB Output is correct
16 Correct 158 ms 38084 KB Output is correct
17 Correct 158 ms 37824 KB Output is correct
18 Correct 164 ms 38340 KB Output is correct
19 Correct 188 ms 41564 KB Output is correct
20 Incorrect 166 ms 43716 KB Output isn't correct
21 Halted 0 ms 0 KB -