제출 #549533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
549533		truc12a2cvp	자매 도시 (APIO20_swap)	C++14	6 / 100	368 ms	45632 KiB

swap

#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)]];
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27