oj.uz

Submission #982650

# Submission time Handle Problem Language Result Execution time Memory
982650 2024-05-14T15:01:42 Z vjudge1 Swapping Cities (APIO20_swap) C++17
13 / 100
 255 ms 79040 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+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 7 ms 37212 KB Output is correct
2 Correct 8 ms 37212 KB Output is correct
3 Correct 7 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37348 KB Output is correct
7 Correct 8 ms 37212 KB Output is correct
8 Correct 7 ms 37464 KB Output is correct
9 Correct 87 ms 63696 KB Output is correct
10 Correct 118 ms 67268 KB Output is correct
11 Correct 130 ms 64968 KB Output is correct
12 Correct 111 ms 69576 KB Output is correct
13 Correct 91 ms 73416 KB Output is correct
14 Correct 94 ms 61892 KB Output is correct
15 Correct 180 ms 68808 KB Output is correct
16 Correct 185 ms 66500 KB Output is correct
17 Correct 185 ms 71108 KB Output is correct
18 Correct 255 ms 74948 KB Output is correct
19 Correct 73 ms 46008 KB Output is correct
20 Correct 180 ms 69064 KB Output is correct
21 Correct 176 ms 68908 KB Output is correct
22 Correct 197 ms 73364 KB Output is correct
23 Correct 217 ms 77224 KB Output is correct

Subtask #2
7.0 / 7.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 186 ms 74232 KB Output is correct
4 Correct 183 ms 78996 KB Output is correct
5 Correct 195 ms 76836 KB Output is correct
6 Correct 185 ms 78948 KB Output is correct
7 Correct 187 ms 79040 KB Output is correct
8 Correct 188 ms 74172 KB Output is correct
9 Correct 234 ms 76704 KB Output is correct
10 Correct 180 ms 74132 KB Output is correct

Subtask #3
0 / 17.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 7 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37348 KB Output is correct
7 Correct 8 ms 37212 KB Output is correct
8 Correct 7 ms 37464 KB Output is correct
9 Correct 7 ms 37212 KB Output is correct
10 Correct 8 ms 37468 KB Output is correct
11 Correct 8 ms 37212 KB Output is correct
12 Correct 8 ms 37468 KB Output is correct
13 Correct 8 ms 37212 KB Output is correct
14 Correct 8 ms 37468 KB Output is correct
15 Correct 8 ms 37208 KB Output is correct
16 Correct 8 ms 37212 KB Output is correct
17 Correct 7 ms 37500 KB Output is correct
18 Correct 7 ms 37464 KB Output is correct
19 Correct 8 ms 37468 KB Output is correct
20 Incorrect 8 ms 37212 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 7 ms 37212 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 7 ms 37212 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37212 KB Output is correct
7 Correct 8 ms 37348 KB Output is correct
8 Correct 8 ms 37212 KB Output is correct
9 Correct 7 ms 37464 KB Output is correct
10 Correct 87 ms 63696 KB Output is correct
11 Correct 118 ms 67268 KB Output is correct
12 Correct 130 ms 64968 KB Output is correct
13 Correct 111 ms 69576 KB Output is correct
14 Correct 91 ms 73416 KB Output is correct
15 Correct 8 ms 37468 KB Output is correct
16 Correct 8 ms 37212 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 Correct 8 ms 37208 KB Output is correct
21 Correct 8 ms 37212 KB Output is correct
22 Correct 7 ms 37500 KB Output is correct
23 Correct 7 ms 37464 KB Output is correct
24 Correct 8 ms 37468 KB Output is correct
25 Incorrect 8 ms 37212 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 7 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37348 KB Output is correct
7 Correct 8 ms 37212 KB Output is correct
8 Correct 7 ms 37464 KB Output is correct
9 Correct 87 ms 63696 KB Output is correct
10 Correct 118 ms 67268 KB Output is correct
11 Correct 130 ms 64968 KB Output is correct
12 Correct 111 ms 69576 KB Output is correct
13 Correct 91 ms 73416 KB Output is correct
14 Correct 94 ms 61892 KB Output is correct
15 Correct 180 ms 68808 KB Output is correct
16 Correct 185 ms 66500 KB Output is correct
17 Correct 185 ms 71108 KB Output is correct
18 Correct 255 ms 74948 KB Output is correct
19 Correct 186 ms 74232 KB Output is correct
20 Correct 183 ms 78996 KB Output is correct
21 Correct 195 ms 76836 KB Output is correct
22 Correct 185 ms 78948 KB Output is correct
23 Correct 187 ms 79040 KB Output is correct
24 Correct 188 ms 74172 KB Output is correct
25 Correct 234 ms 76704 KB Output is correct
26 Correct 180 ms 74132 KB Output is correct
27 Correct 8 ms 37468 KB Output is correct
28 Correct 8 ms 37212 KB Output is correct
29 Correct 8 ms 37468 KB Output is correct
30 Correct 8 ms 37212 KB Output is correct
31 Correct 8 ms 37468 KB Output is correct
32 Correct 8 ms 37208 KB Output is correct
33 Correct 8 ms 37212 KB Output is correct
34 Correct 7 ms 37500 KB Output is correct
35 Correct 7 ms 37464 KB Output is correct
36 Correct 17 ms 42524 KB Output is correct
37 Correct 123 ms 69540 KB Output is correct
38 Correct 118 ms 71212 KB Output is correct
39 Correct 122 ms 69572 KB Output is correct
40 Correct 109 ms 67552 KB Output is correct
41 Correct 121 ms 68272 KB Output is correct
42 Correct 100 ms 64720 KB Output is correct
43 Correct 122 ms 69572 KB Output is correct
44 Correct 111 ms 66640 KB Output is correct
45 Correct 97 ms 74692 KB Output is correct
46 Correct 114 ms 71272 KB Output is correct
47 Incorrect 27 ms 40580 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 7 ms 37212 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 7 ms 37212 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37212 KB Output is correct
7 Correct 8 ms 37348 KB Output is correct
8 Correct 8 ms 37212 KB Output is correct
9 Correct 7 ms 37464 KB Output is correct
10 Correct 87 ms 63696 KB Output is correct
11 Correct 118 ms 67268 KB Output is correct
12 Correct 130 ms 64968 KB Output is correct
13 Correct 111 ms 69576 KB Output is correct
14 Correct 91 ms 73416 KB Output is correct
15 Correct 94 ms 61892 KB Output is correct
16 Correct 180 ms 68808 KB Output is correct
17 Correct 185 ms 66500 KB Output is correct
18 Correct 185 ms 71108 KB Output is correct
19 Correct 255 ms 74948 KB Output is correct
20 Correct 186 ms 74232 KB Output is correct
21 Correct 183 ms 78996 KB Output is correct
22 Correct 195 ms 76836 KB Output is correct
23 Correct 185 ms 78948 KB Output is correct
24 Correct 187 ms 79040 KB Output is correct
25 Correct 188 ms 74172 KB Output is correct
26 Correct 234 ms 76704 KB Output is correct
27 Correct 180 ms 74132 KB Output is correct
28 Correct 8 ms 37468 KB Output is correct
29 Correct 8 ms 37212 KB Output is correct
30 Correct 8 ms 37468 KB Output is correct
31 Correct 8 ms 37212 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 37212 KB Output is correct
35 Correct 7 ms 37500 KB Output is correct
36 Correct 7 ms 37464 KB Output is correct
37 Correct 17 ms 42524 KB Output is correct
38 Correct 123 ms 69540 KB Output is correct
39 Correct 118 ms 71212 KB Output is correct
40 Correct 122 ms 69572 KB Output is correct
41 Correct 109 ms 67552 KB Output is correct
42 Correct 121 ms 68272 KB Output is correct
43 Correct 100 ms 64720 KB Output is correct
44 Correct 122 ms 69572 KB Output is correct
45 Correct 111 ms 66640 KB Output is correct
46 Correct 97 ms 74692 KB Output is correct
47 Correct 114 ms 71272 KB Output is correct
48 Incorrect 27 ms 40580 KB Output isn't correct
49 Halted 0 ms 0 KB -