oj.uz

Submission #982635

# Submission time Handle Problem Language Result Execution time Memory
982635 2024-05-14T14:29:51 Z vjudge1 Swapping Cities (APIO20_swap) C++17
6 / 100
 231 ms 46700 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];

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);
      bool is=(sz(g[u])>2||sz(g[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";
  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 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12768 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 81 ms 34000 KB Output is correct
10 Correct 93 ms 37352 KB Output is correct
11 Correct 88 ms 37320 KB Output is correct
12 Correct 95 ms 39880 KB Output is correct
13 Correct 81 ms 42948 KB Output is correct
14 Correct 79 ms 34120 KB Output is correct
15 Correct 162 ms 43128 KB Output is correct
16 Correct 178 ms 40804 KB Output is correct
17 Correct 172 ms 43128 KB Output is correct
18 Correct 180 ms 46584 KB Output is correct
19 Correct 66 ms 21024 KB Output is correct
20 Correct 161 ms 43304 KB Output is correct
21 Correct 161 ms 41268 KB Output is correct
22 Correct 180 ms 43556 KB Output is correct
23 Correct 231 ms 46700 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Incorrect 162 ms 46280 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 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12768 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Incorrect 4 ms 12636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 4 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Correct 3 ms 12768 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 81 ms 34000 KB Output is correct
11 Correct 93 ms 37352 KB Output is correct
12 Correct 88 ms 37320 KB Output is correct
13 Correct 95 ms 39880 KB Output is correct
14 Correct 81 ms 42948 KB Output is correct
15 Incorrect 4 ms 12636 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12768 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 81 ms 34000 KB Output is correct
10 Correct 93 ms 37352 KB Output is correct
11 Correct 88 ms 37320 KB Output is correct
12 Correct 95 ms 39880 KB Output is correct
13 Correct 81 ms 42948 KB Output is correct
14 Correct 79 ms 34120 KB Output is correct
15 Correct 162 ms 43128 KB Output is correct
16 Correct 178 ms 40804 KB Output is correct
17 Correct 172 ms 43128 KB Output is correct
18 Correct 180 ms 46584 KB Output is correct
19 Incorrect 162 ms 46280 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 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 4 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Correct 3 ms 12768 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 81 ms 34000 KB Output is correct
11 Correct 93 ms 37352 KB Output is correct
12 Correct 88 ms 37320 KB Output is correct
13 Correct 95 ms 39880 KB Output is correct
14 Correct 81 ms 42948 KB Output is correct
15 Correct 79 ms 34120 KB Output is correct
16 Correct 162 ms 43128 KB Output is correct
17 Correct 178 ms 40804 KB Output is correct
18 Correct 172 ms 43128 KB Output is correct
19 Correct 180 ms 46584 KB Output is correct
20 Incorrect 162 ms 46280 KB Output isn't correct
21 Halted 0 ms 0 KB -