oj.uz

Submission #982641

# Submission time Handle Problem Language Result Execution time Memory
982641 2024-05-14T14:38:24 Z vjudge1 Swapping Cities (APIO20_swap) C++17
13 / 100
 207 ms 48140 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)){
      // g[u].pb(v);
      // g[v].pb(v);
      deg[u]++;
      deg[v]++;
      bool is=(deg[u]>2||deg[v]>2);
      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 3 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 90 ms 33836 KB Output is correct
10 Correct 92 ms 36388 KB Output is correct
11 Correct 87 ms 36292 KB Output is correct
12 Correct 94 ms 36808 KB Output is correct
13 Correct 81 ms 39876 KB Output is correct
14 Correct 77 ms 32708 KB Output is correct
15 Correct 160 ms 38092 KB Output is correct
16 Correct 156 ms 37792 KB Output is correct
17 Correct 184 ms 38340 KB Output is correct
18 Correct 181 ms 41420 KB Output is correct
19 Correct 65 ms 21388 KB Output is correct
20 Correct 161 ms 38404 KB Output is correct
21 Correct 163 ms 39464 KB Output is correct
22 Correct 181 ms 39872 KB Output is correct
23 Correct 187 ms 43188 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 168 ms 44044 KB Output is correct
4 Correct 175 ms 48140 KB Output is correct
5 Correct 207 ms 48068 KB Output is correct
6 Correct 186 ms 48024 KB Output is correct
7 Correct 171 ms 48072 KB Output is correct
8 Correct 173 ms 47296 KB Output is correct
9 Correct 170 ms 47812 KB Output is correct
10 Correct 194 ms 47252 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 3 ms 14684 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 3 ms 14684 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 2 ms 14684 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 4 ms 14684 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 90 ms 33836 KB Output is correct
11 Correct 92 ms 36388 KB Output is correct
12 Correct 87 ms 36292 KB Output is correct
13 Correct 94 ms 36808 KB Output is correct
14 Correct 81 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 3 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 90 ms 33836 KB Output is correct
10 Correct 92 ms 36388 KB Output is correct
11 Correct 87 ms 36292 KB Output is correct
12 Correct 94 ms 36808 KB Output is correct
13 Correct 81 ms 39876 KB Output is correct
14 Correct 77 ms 32708 KB Output is correct
15 Correct 160 ms 38092 KB Output is correct
16 Correct 156 ms 37792 KB Output is correct
17 Correct 184 ms 38340 KB Output is correct
18 Correct 181 ms 41420 KB Output is correct
19 Correct 168 ms 44044 KB Output is correct
20 Correct 175 ms 48140 KB Output is correct
21 Correct 207 ms 48068 KB Output is correct
22 Correct 186 ms 48024 KB Output is correct
23 Correct 171 ms 48072 KB Output is correct
24 Correct 173 ms 47296 KB Output is correct
25 Correct 170 ms 47812 KB Output is correct
26 Correct 194 ms 47252 KB Output is correct
27 Correct 3 ms 14684 KB Output is correct
28 Incorrect 3 ms 14684 KB Output isn't correct
29 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 14680 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 2 ms 14684 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 4 ms 14684 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 90 ms 33836 KB Output is correct
11 Correct 92 ms 36388 KB Output is correct
12 Correct 87 ms 36292 KB Output is correct
13 Correct 94 ms 36808 KB Output is correct
14 Correct 81 ms 39876 KB Output is correct
15 Correct 77 ms 32708 KB Output is correct
16 Correct 160 ms 38092 KB Output is correct
17 Correct 156 ms 37792 KB Output is correct
18 Correct 184 ms 38340 KB Output is correct
19 Correct 181 ms 41420 KB Output is correct
20 Correct 168 ms 44044 KB Output is correct
21 Correct 175 ms 48140 KB Output is correct
22 Correct 207 ms 48068 KB Output is correct
23 Correct 186 ms 48024 KB Output is correct
24 Correct 171 ms 48072 KB Output is correct
25 Correct 173 ms 47296 KB Output is correct
26 Correct 170 ms 47812 KB Output is correct
27 Correct 194 ms 47252 KB Output is correct
28 Correct 3 ms 14684 KB Output is correct
29 Incorrect 3 ms 14684 KB Output isn't correct
30 Halted 0 ms 0 KB -