oj.uz

Submission #982653

# Submission time Handle Problem Language Result Execution time Memory
982653 2024-05-14T15:03:00 Z vjudge1 Swapping Cities (APIO20_swap) C++17
13 / 100
 223 ms 77352 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=1e6+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){
  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,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 8 ms 37212 KB Output is correct
2 Correct 5 ms 25176 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 7 ms 25436 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 8 ms 37468 KB Output is correct
9 Correct 86 ms 59788 KB Output is correct
10 Correct 125 ms 67272 KB Output is correct
11 Correct 105 ms 63252 KB Output is correct
12 Correct 118 ms 69572 KB Output is correct
13 Correct 103 ms 73744 KB Output is correct
14 Correct 101 ms 59968 KB Output is correct
15 Correct 200 ms 53960 KB Output is correct
16 Correct 180 ms 63448 KB Output is correct
17 Correct 210 ms 63176 KB Output is correct
18 Correct 203 ms 73160 KB Output is correct
19 Correct 73 ms 45780 KB Output is correct
20 Correct 194 ms 66200 KB Output is correct
21 Correct 178 ms 67124 KB Output is correct
22 Correct 201 ms 70316 KB Output is correct
23 Correct 223 ms 77352 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37212 KB Output is correct
2 Correct 5 ms 25176 KB Output is correct
3 Correct 187 ms 74248 KB Output is correct
4 Correct 203 ms 77204 KB Output is correct
5 Correct 214 ms 74992 KB Output is correct
6 Correct 192 ms 76952 KB Output is correct
7 Correct 188 ms 77036 KB Output is correct
8 Correct 190 ms 74276 KB Output is correct
9 Correct 184 ms 76740 KB Output is correct
10 Correct 191 ms 74248 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37212 KB Output is correct
2 Correct 5 ms 25176 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 7 ms 25436 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 8 ms 37468 KB Output is correct
9 Correct 7 ms 37212 KB Output is correct
10 Correct 8 ms 37472 KB Output is correct
11 Correct 7 ms 37212 KB Output is correct
12 Correct 7 ms 37468 KB Output is correct
13 Correct 8 ms 37212 KB Output is correct
14 Correct 7 ms 37464 KB Output is correct
15 Correct 8 ms 37468 KB Output is correct
16 Correct 8 ms 37208 KB Output is correct
17 Correct 8 ms 37468 KB Output is correct
18 Correct 8 ms 37212 KB Output is correct
19 Correct 8 ms 37468 KB Output is correct
20 Incorrect 7 ms 37208 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37212 KB Output is correct
2 Correct 8 ms 37212 KB Output is correct
3 Correct 5 ms 25176 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 9 ms 37212 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 7 ms 25436 KB Output is correct
9 Correct 8 ms 37468 KB Output is correct
10 Correct 86 ms 59788 KB Output is correct
11 Correct 125 ms 67272 KB Output is correct
12 Correct 105 ms 63252 KB Output is correct
13 Correct 118 ms 69572 KB Output is correct
14 Correct 103 ms 73744 KB Output is correct
15 Correct 8 ms 37472 KB Output is correct
16 Correct 7 ms 37212 KB Output is correct
17 Correct 7 ms 37468 KB Output is correct
18 Correct 8 ms 37212 KB Output is correct
19 Correct 7 ms 37464 KB Output is correct
20 Correct 8 ms 37468 KB Output is correct
21 Correct 8 ms 37208 KB Output is correct
22 Correct 8 ms 37468 KB Output is correct
23 Correct 8 ms 37212 KB Output is correct
24 Correct 8 ms 37468 KB Output is correct
25 Incorrect 7 ms 37208 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37212 KB Output is correct
2 Correct 5 ms 25176 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 7 ms 25436 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 8 ms 37468 KB Output is correct
9 Correct 86 ms 59788 KB Output is correct
10 Correct 125 ms 67272 KB Output is correct
11 Correct 105 ms 63252 KB Output is correct
12 Correct 118 ms 69572 KB Output is correct
13 Correct 103 ms 73744 KB Output is correct
14 Correct 101 ms 59968 KB Output is correct
15 Correct 200 ms 53960 KB Output is correct
16 Correct 180 ms 63448 KB Output is correct
17 Correct 210 ms 63176 KB Output is correct
18 Correct 203 ms 73160 KB Output is correct
19 Correct 187 ms 74248 KB Output is correct
20 Correct 203 ms 77204 KB Output is correct
21 Correct 214 ms 74992 KB Output is correct
22 Correct 192 ms 76952 KB Output is correct
23 Correct 188 ms 77036 KB Output is correct
24 Correct 190 ms 74276 KB Output is correct
25 Correct 184 ms 76740 KB Output is correct
26 Correct 191 ms 74248 KB Output is correct
27 Correct 8 ms 37472 KB Output is correct
28 Correct 7 ms 37212 KB Output is correct
29 Correct 7 ms 37468 KB Output is correct
30 Correct 8 ms 37212 KB Output is correct
31 Correct 7 ms 37464 KB Output is correct
32 Correct 8 ms 37468 KB Output is correct
33 Correct 8 ms 37208 KB Output is correct
34 Correct 8 ms 37468 KB Output is correct
35 Correct 8 ms 37212 KB Output is correct
36 Correct 16 ms 42520 KB Output is correct
37 Correct 112 ms 69580 KB Output is correct
38 Correct 129 ms 71364 KB Output is correct
39 Correct 109 ms 69576 KB Output is correct
40 Correct 111 ms 69320 KB Output is correct
41 Correct 112 ms 69320 KB Output is correct
42 Correct 101 ms 64640 KB Output is correct
43 Correct 115 ms 71368 KB Output is correct
44 Correct 114 ms 69576 KB Output is correct
45 Correct 91 ms 74608 KB Output is correct
46 Correct 119 ms 71408 KB Output is correct
47 Incorrect 23 ms 40584 KB Output isn't correct
48 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37212 KB Output is correct
2 Correct 8 ms 37212 KB Output is correct
3 Correct 5 ms 25176 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 9 ms 37212 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 7 ms 25436 KB Output is correct
9 Correct 8 ms 37468 KB Output is correct
10 Correct 86 ms 59788 KB Output is correct
11 Correct 125 ms 67272 KB Output is correct
12 Correct 105 ms 63252 KB Output is correct
13 Correct 118 ms 69572 KB Output is correct
14 Correct 103 ms 73744 KB Output is correct
15 Correct 101 ms 59968 KB Output is correct
16 Correct 200 ms 53960 KB Output is correct
17 Correct 180 ms 63448 KB Output is correct
18 Correct 210 ms 63176 KB Output is correct
19 Correct 203 ms 73160 KB Output is correct
20 Correct 187 ms 74248 KB Output is correct
21 Correct 203 ms 77204 KB Output is correct
22 Correct 214 ms 74992 KB Output is correct
23 Correct 192 ms 76952 KB Output is correct
24 Correct 188 ms 77036 KB Output is correct
25 Correct 190 ms 74276 KB Output is correct
26 Correct 184 ms 76740 KB Output is correct
27 Correct 191 ms 74248 KB Output is correct
28 Correct 8 ms 37472 KB Output is correct
29 Correct 7 ms 37212 KB Output is correct
30 Correct 7 ms 37468 KB Output is correct
31 Correct 8 ms 37212 KB Output is correct
32 Correct 7 ms 37464 KB Output is correct
33 Correct 8 ms 37468 KB Output is correct
34 Correct 8 ms 37208 KB Output is correct
35 Correct 8 ms 37468 KB Output is correct
36 Correct 8 ms 37212 KB Output is correct
37 Correct 16 ms 42520 KB Output is correct
38 Correct 112 ms 69580 KB Output is correct
39 Correct 129 ms 71364 KB Output is correct
40 Correct 109 ms 69576 KB Output is correct
41 Correct 111 ms 69320 KB Output is correct
42 Correct 112 ms 69320 KB Output is correct
43 Correct 101 ms 64640 KB Output is correct
44 Correct 115 ms 71368 KB Output is correct
45 Correct 114 ms 69576 KB Output is correct
46 Correct 91 ms 74608 KB Output is correct
47 Correct 119 ms 71408 KB Output is correct
48 Incorrect 23 ms 40584 KB Output isn't correct
49 Halted 0 ms 0 KB -