oj.uz

Submission #549533

# Submission time Handle Problem Language Result Execution time Memory
549533 2022-04-16T02:39:31 Z truc12a2cvp Swapping Cities (APIO20_swap) C++14
6 / 100
 368 ms 45632 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> II;
const int maxn = 3e5 + 5, logN = 20;
const int MOD = 1e9 + 7;
const ll INF = 1e9;

struct edge{
       int u, v, w;
       edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}
       bool operator < (const edge &op) const{
              return w < op.w;
       }
}ed[maxn];

int n, m, par[maxn], f[maxn][logN], up[maxn], L[maxn], R[maxn], depth[maxn], val[maxn];
vector<int> g[maxn];
bool isline[maxn];

int get(int u){
       if(par[u] != u) par[u] = get(par[u]);
       return par[u];
}

void dfs(int u, int p){
       up[u] = ((isline[u] == false) ? u : up[p]);
       depth[u] = depth[p] + 1;
       f[u][0] = p;
       for(int i = 1; i < logN; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
       for(int v : g[u]){
              dfs(v, u);
       }
}

int lca(int u, int v){
       if(depth[u] < depth[v]) swap(u, v);
       for(int i = logN - 1; i >= 0; i --){
              if(depth[f[u][i]] >= depth[v]) u = f[u][i];
       }
       if(u == v) return u;
       for(int i = logN - 1; i >= 0; i --){
              if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
       }
       return f[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
       n = N, m = M;
       for(int i = 1; i <= m; i ++) ed[i] = edge(U[i - 1] + 1, V[i - 1] + 1, W[i - 1]);
       sort(ed + 1, ed + m + 1);
       for(int i = 1; i <= n; i ++) L[i] = R[i] = i, isline[i] = true;
       for(int i = 1; i <= n + m; i ++) par[i] = i;
       for(int i = 1; i <= m; i ++){
              int u = ed[i].u, v = ed[i].v, w = ed[i].w;
              u = get(u), v = get(v);
              par[u] = par[v] = i + n;
              val[i + n] = w;
              isline[i + n] = (isline[u] && isline[v] && (u != v));
              bool flag = false;
              if(isline[i + n]){
                     bool flag = false;
                     for(int x : {L[u], R[u]}){
                            for(int y : {L[v], R[v]}){
                                   if((x == ed[i].u && y == ed[i].v) || (x == ed[i].v, y = ed[i].u)){
                                          L[i + n] = L[u] ^ R[u] ^ x;
                                          R[i + n] = L[v] ^ R[v] ^ y;
                                          flag = true;
                                          break;
                                   }
                            }
                     }
                     isline[i + n] &= flag;
              }
              g[i + n].push_back(u);
              if(u != v) g[i + n].push_back(v);
       }
       dfs(n + m, 0);
}

int getMinimumFuelCapacity(int X, int Y){
       if(isline[n + m]) return -1;
       return val[up[lca(X + 1, Y + 1)]];
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:65:76: warning: left operand of comma operator has no effect [-Wunused-value]
   65 |                                    if((x == ed[i].u && y == ed[i].v) || (x == ed[i].v, y = ed[i].u)){
      |                                                                          ~~^~~~~~~~~~
swap.cpp:65:90: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   65 |                                    if((x == ed[i].u && y == ed[i].v) || (x == ed[i].v, y = ed[i].u)){
      |                                                                                        ~~^~~~~~~~~
swap.cpp:60:20: warning: unused variable 'flag' [-Wunused-variable]
   60 |               bool flag = false;
      |                    ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 6 ms 10900 KB Output is correct
3 Correct 6 ms 10836 KB Output is correct
4 Correct 6 ms 10980 KB Output is correct
5 Correct 6 ms 11160 KB Output is correct
6 Correct 6 ms 11108 KB Output is correct
7 Correct 6 ms 11172 KB Output is correct
8 Correct 6 ms 11152 KB Output is correct
9 Correct 92 ms 32652 KB Output is correct
10 Correct 144 ms 37568 KB Output is correct
11 Correct 127 ms 37196 KB Output is correct
12 Correct 127 ms 38668 KB Output is correct
13 Correct 99 ms 40240 KB Output is correct
14 Correct 104 ms 33016 KB Output is correct
15 Correct 180 ms 41968 KB Output is correct
16 Correct 164 ms 41080 KB Output is correct
17 Correct 195 ms 42792 KB Output is correct
18 Correct 159 ms 44300 KB Output is correct
19 Correct 110 ms 20396 KB Output is correct
20 Correct 254 ms 43080 KB Output is correct
21 Correct 266 ms 42224 KB Output is correct
22 Correct 271 ms 44204 KB Output is correct
23 Correct 368 ms 45632 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 6 ms 10900 KB Output is correct
3 Incorrect 136 ms 43656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 6 ms 10900 KB Output is correct
3 Correct 6 ms 10836 KB Output is correct
4 Correct 6 ms 10980 KB Output is correct
5 Correct 6 ms 11160 KB Output is correct
6 Correct 6 ms 11108 KB Output is correct
7 Correct 6 ms 11172 KB Output is correct
8 Correct 6 ms 11152 KB Output is correct
9 Correct 6 ms 10824 KB Output is correct
10 Incorrect 7 ms 11152 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10824 KB Output is correct
2 Correct 6 ms 10836 KB Output is correct
3 Correct 6 ms 10900 KB Output is correct
4 Correct 6 ms 10836 KB Output is correct
5 Correct 6 ms 10980 KB Output is correct
6 Correct 6 ms 11160 KB Output is correct
7 Correct 6 ms 11108 KB Output is correct
8 Correct 6 ms 11172 KB Output is correct
9 Correct 6 ms 11152 KB Output is correct
10 Correct 92 ms 32652 KB Output is correct
11 Correct 144 ms 37568 KB Output is correct
12 Correct 127 ms 37196 KB Output is correct
13 Correct 127 ms 38668 KB Output is correct
14 Correct 99 ms 40240 KB Output is correct
15 Incorrect 7 ms 11152 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 6 ms 10900 KB Output is correct
3 Correct 6 ms 10836 KB Output is correct
4 Correct 6 ms 10980 KB Output is correct
5 Correct 6 ms 11160 KB Output is correct
6 Correct 6 ms 11108 KB Output is correct
7 Correct 6 ms 11172 KB Output is correct
8 Correct 6 ms 11152 KB Output is correct
9 Correct 92 ms 32652 KB Output is correct
10 Correct 144 ms 37568 KB Output is correct
11 Correct 127 ms 37196 KB Output is correct
12 Correct 127 ms 38668 KB Output is correct
13 Correct 99 ms 40240 KB Output is correct
14 Correct 104 ms 33016 KB Output is correct
15 Correct 180 ms 41968 KB Output is correct
16 Correct 164 ms 41080 KB Output is correct
17 Correct 195 ms 42792 KB Output is correct
18 Correct 159 ms 44300 KB Output is correct
19 Incorrect 136 ms 43656 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10824 KB Output is correct
2 Correct 6 ms 10836 KB Output is correct
3 Correct 6 ms 10900 KB Output is correct
4 Correct 6 ms 10836 KB Output is correct
5 Correct 6 ms 10980 KB Output is correct
6 Correct 6 ms 11160 KB Output is correct
7 Correct 6 ms 11108 KB Output is correct
8 Correct 6 ms 11172 KB Output is correct
9 Correct 6 ms 11152 KB Output is correct
10 Correct 92 ms 32652 KB Output is correct
11 Correct 144 ms 37568 KB Output is correct
12 Correct 127 ms 37196 KB Output is correct
13 Correct 127 ms 38668 KB Output is correct
14 Correct 99 ms 40240 KB Output is correct
15 Correct 104 ms 33016 KB Output is correct
16 Correct 180 ms 41968 KB Output is correct
17 Correct 164 ms 41080 KB Output is correct
18 Correct 195 ms 42792 KB Output is correct
19 Correct 159 ms 44300 KB Output is correct
20 Incorrect 136 ms 43656 KB Output isn't correct
21 Halted 0 ms 0 KB -