oj.uz

Submission #701375

# Submission time Handle Problem Language Result Execution time Memory
701375 2023-02-21T05:05:41 Z Quan2003 Swapping Cities (APIO20_swap) C++17
6 / 100
 354 ms 48344 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;
bool invalid; 
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];
int deg[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];
              deg[U[i]]++; deg[V[i]]++; 
              edges[i].w = W[i]; 
         }
         sort(edges,edges + M,cmp);
         E = N;
         for(int i = 1; i <= n; i++) if(deg[i] == 3) invalid = invalid || 1;
         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);
      if(!invalid){
         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:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     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 7508 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7620 KB Output is correct
5 Correct 5 ms 7764 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7876 KB Output is correct
9 Correct 113 ms 32716 KB Output is correct
10 Correct 136 ms 38456 KB Output is correct
11 Correct 136 ms 37876 KB Output is correct
12 Correct 156 ms 39740 KB Output is correct
13 Correct 109 ms 42888 KB Output is correct
14 Correct 121 ms 33024 KB Output is correct
15 Correct 329 ms 42812 KB Output is correct
16 Correct 270 ms 41864 KB Output is correct
17 Correct 284 ms 43848 KB Output is correct
18 Correct 354 ms 46892 KB Output is correct
19 Correct 83 ms 17664 KB Output is correct
20 Correct 288 ms 43872 KB Output is correct
21 Correct 276 ms 43044 KB Output is correct
22 Correct 300 ms 45140 KB Output is correct
23 Correct 347 ms 48344 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 7508 KB Output is correct
3 Incorrect 317 ms 46196 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 7508 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7620 KB Output is correct
5 Correct 5 ms 7764 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7876 KB Output is correct
9 Correct 4 ms 7496 KB Output is correct
10 Incorrect 6 ms 7808 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 7496 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 4 ms 7620 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7764 KB Output is correct
9 Correct 5 ms 7876 KB Output is correct
10 Correct 113 ms 32716 KB Output is correct
11 Correct 136 ms 38456 KB Output is correct
12 Correct 136 ms 37876 KB Output is correct
13 Correct 156 ms 39740 KB Output is correct
14 Correct 109 ms 42888 KB Output is correct
15 Incorrect 6 ms 7808 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 7508 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7620 KB Output is correct
5 Correct 5 ms 7764 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7876 KB Output is correct
9 Correct 113 ms 32716 KB Output is correct
10 Correct 136 ms 38456 KB Output is correct
11 Correct 136 ms 37876 KB Output is correct
12 Correct 156 ms 39740 KB Output is correct
13 Correct 109 ms 42888 KB Output is correct
14 Correct 121 ms 33024 KB Output is correct
15 Correct 329 ms 42812 KB Output is correct
16 Correct 270 ms 41864 KB Output is correct
17 Correct 284 ms 43848 KB Output is correct
18 Correct 354 ms 46892 KB Output is correct
19 Incorrect 317 ms 46196 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 7496 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 4 ms 7620 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7764 KB Output is correct
9 Correct 5 ms 7876 KB Output is correct
10 Correct 113 ms 32716 KB Output is correct
11 Correct 136 ms 38456 KB Output is correct
12 Correct 136 ms 37876 KB Output is correct
13 Correct 156 ms 39740 KB Output is correct
14 Correct 109 ms 42888 KB Output is correct
15 Correct 121 ms 33024 KB Output is correct
16 Correct 329 ms 42812 KB Output is correct
17 Correct 270 ms 41864 KB Output is correct
18 Correct 284 ms 43848 KB Output is correct
19 Correct 354 ms 46892 KB Output is correct
20 Incorrect 317 ms 46196 KB Output isn't correct
21 Halted 0 ms 0 KB -