oj.uz

Submission #701130

# Submission time Handle Problem Language Result Execution time Memory
701130 2023-02-20T07:06:11 Z Quan2003 Swapping Cities (APIO20_swap) C++17
6 / 100
 367 ms 47960 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 100;
const int INF = 1e7 + 10; 
long long n,m,q,dsz,E;
int timer = 1;
vector<int>adj[N + 1];
int fa[N + 1];
bool cyc[N + 1]; 
int up[23][N + 1],dp[N + 1],val[N + 1];
int lf[N + 1],ri[N + 1]; 
int in[N + 1],to[N + 1]; 
struct edge{
     int w,u,v;
} edges[N + 1]; 
int find(int u){
     if(u == fa[u]) return u;
     return fa[u] = find(fa[u]); 
}
void dfs_calc(int u){
    to[timer] = u; 
    in[u] = timer++; 
    for(int i = 1; i < 23 ; i++){
        up[i][u] = up[i - 1][up[i - 1][u]];
    }
    for(int i = 0; i < adj[u].size(); i++){
        int v = adj[u][i]; 
        if(v == up[0][u]) continue;
        dp[v] = dp[up[0][v] = u] + 1;      
        dfs_calc(v);
    }
}
int lca(int a, int b){
    if(dp[a] < dp[b]) swap(a,b);
    int d = dp[a] - dp[b];
    for(int i = 0; i < 23 ; i++){
        if( (d >> i) & 1) a = up[i][a];
    }
    if(a == b) return a;
    for(int i = 22; i >= 0; i--){
         int tA = up[i][a]; int tB = up[i][b];
         if(tA != tB) {
            a = tA; b = tB;
         }
    } 
    return up[0][a];
} 
bool cmp(edge &a, edge &b){
     return a.w < b.w; 
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W){
         for(int i = 0; i < M; i++){
              edges[i].u = ++U[i]; edges[i].v = ++V[i];
              edges[i].w = W[i]; 
         }
         sort(edges,edges + M,cmp);
         E = N;
         for(int i = 1; i <= N; i++) fa[i] = i; 
         for(int i = 0; i < M; i++){
              int x = find(edges[i].u); int y = find(edges[i].v);
              E++; 
              if(x == y){
                   fa[x] = fa[E] = E;
                   adj[E].push_back(x); 
                   val[E] = edges[i].w;
                   cyc[E] = 1; 
              }
              else{
                   if(x < y) swap(x,y); 
                   fa[x] = fa[y] = fa[E] = E; 
                   adj[E].push_back(x);
                   adj[E].push_back(y); 
                   val[E] = edges[i].w;
              }
         }
         dfs_calc(E);
         stack<pair<int,int>>stk; 
         stk.push({2,0});
         for(int i = 1; i <= E; i++){
              int u = to[i]; 
              while(stk.size() and stk.top().first <= cyc[u]) stk.pop(); 
              lf[u] = stk.top().second; 
              stk.push({cyc[u],u});             
         }
         while(stk.size()) stk.pop();
         stk.push({2,0});
         for(int i = E; i > 0; i--){
              int u = to[i];
              while(stk.size() and stk.top().first <= cyc[u]) stk.pop();
              ri[u] = stk.top().second;   
              stk.push({cyc[u],u}); 
         }
}
int getMinimumFuelCapacity(int X, int Y){
      int anc = lca(++X,++Y);
      //cout<<anc<<endl;
      if(cyc[anc] or ri[anc]) return val[anc];
      if(lf[anc]) return val[lf[anc]];
      return -1;
      
}

Compilation message

swap.cpp: In function 'void dfs_calc(int)':
swap.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0; i < adj[u].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7488 KB Output is correct
3 Correct 5 ms 7508 KB Output is correct
4 Correct 5 ms 7636 KB Output is correct
5 Correct 5 ms 7836 KB Output is correct
6 Correct 4 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7892 KB Output is correct
9 Correct 119 ms 32520 KB Output is correct
10 Correct 131 ms 38044 KB Output is correct
11 Correct 136 ms 37628 KB Output is correct
12 Correct 158 ms 39248 KB Output is correct
13 Correct 102 ms 42440 KB Output is correct
14 Correct 133 ms 32716 KB Output is correct
15 Correct 305 ms 42316 KB Output is correct
16 Correct 288 ms 41468 KB Output is correct
17 Correct 291 ms 43432 KB Output is correct
18 Correct 328 ms 46540 KB Output is correct
19 Correct 84 ms 17632 KB Output is correct
20 Correct 284 ms 43468 KB Output is correct
21 Correct 281 ms 42656 KB Output is correct
22 Correct 282 ms 44840 KB Output is correct
23 Correct 367 ms 47960 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7488 KB Output is correct
3 Incorrect 303 ms 47016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7488 KB Output is correct
3 Correct 5 ms 7508 KB Output is correct
4 Correct 5 ms 7636 KB Output is correct
5 Correct 5 ms 7836 KB Output is correct
6 Correct 4 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7892 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Incorrect 5 ms 7764 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 4 ms 7488 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 5 ms 7836 KB Output is correct
7 Correct 4 ms 7764 KB Output is correct
8 Correct 5 ms 7764 KB Output is correct
9 Correct 5 ms 7892 KB Output is correct
10 Correct 119 ms 32520 KB Output is correct
11 Correct 131 ms 38044 KB Output is correct
12 Correct 136 ms 37628 KB Output is correct
13 Correct 158 ms 39248 KB Output is correct
14 Correct 102 ms 42440 KB Output is correct
15 Incorrect 5 ms 7764 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7488 KB Output is correct
3 Correct 5 ms 7508 KB Output is correct
4 Correct 5 ms 7636 KB Output is correct
5 Correct 5 ms 7836 KB Output is correct
6 Correct 4 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7892 KB Output is correct
9 Correct 119 ms 32520 KB Output is correct
10 Correct 131 ms 38044 KB Output is correct
11 Correct 136 ms 37628 KB Output is correct
12 Correct 158 ms 39248 KB Output is correct
13 Correct 102 ms 42440 KB Output is correct
14 Correct 133 ms 32716 KB Output is correct
15 Correct 305 ms 42316 KB Output is correct
16 Correct 288 ms 41468 KB Output is correct
17 Correct 291 ms 43432 KB Output is correct
18 Correct 328 ms 46540 KB Output is correct
19 Incorrect 303 ms 47016 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 4 ms 7488 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 5 ms 7836 KB Output is correct
7 Correct 4 ms 7764 KB Output is correct
8 Correct 5 ms 7764 KB Output is correct
9 Correct 5 ms 7892 KB Output is correct
10 Correct 119 ms 32520 KB Output is correct
11 Correct 131 ms 38044 KB Output is correct
12 Correct 136 ms 37628 KB Output is correct
13 Correct 158 ms 39248 KB Output is correct
14 Correct 102 ms 42440 KB Output is correct
15 Correct 133 ms 32716 KB Output is correct
16 Correct 305 ms 42316 KB Output is correct
17 Correct 288 ms 41468 KB Output is correct
18 Correct 291 ms 43432 KB Output is correct
19 Correct 328 ms 46540 KB Output is correct
20 Incorrect 303 ms 47016 KB Output isn't correct
21 Halted 0 ms 0 KB -