제출 #566212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566212		zaneyu	Swapping Cities (APIO20_swap)	C++14	37 / 100	2060 ms	22112 KiB

swap

/*input
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

*/
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
#define MXTO(a,b) a=max(a,b)
#define MNTO(a,b) a=min(a,b)
#define sz(x) (int)x.size()
#define pb push_back
const int maxn=1e5+5;
vector<pair<int,pii>> ed;
int n,m;
vector<pii> g[maxn];
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N,m=M;
    REP(i,M){
        ed.pb({W[i],{U[i],V[i]}});
        g[U[i]].pb({V[i],W[i]});
        g[V[i]].pb({U[i],W[i]});
    }
    sort(ALL(ed));
}
int par[maxn];
pair<bool,pii> cmp[maxn];
int find(int u){
    if(par[u]==u) return u;
    return par[u]=find(par[u]);
}
vector<int> v[maxn];
void merge(int a,int b){
    int oa=a,ob=b;
    a=find(a),b=find(b);
    if(a==b){
        cmp[a].f=0;
        return;
    }
    par[b]=a;
    if(cmp[a].f and cmp[b].f){
        if((oa==cmp[a].s.f or oa==cmp[a].s.s) and (ob==cmp[b].s.f or ob==cmp[b].s.s)){
            cmp[a].f=1;
            if(oa==cmp[a].s.f) cmp[a].s.f=cmp[a].s.s;
            if(ob==cmp[b].s.f) cmp[a].s.s=cmp[b].s.s;
            else cmp[a].s.s=cmp[b].s.f;
        }
        else cmp[a].f=0;
    }
    else cmp[a].f=0;
}
const int INF=0x3f3f3f3f;
int getMinimumFuelCapacity(int x, int y) {
    REP(i,n) par[i]=i,v[i].clear(),cmp[i]={1,{i,i}};
    int ans=-1;
    for(auto a:ed){
        merge(a.s.f,a.s.s);
        if(find(x)==find(y)){
            if(!cmp[find(x)].f){
                return a.f;
            }
        }
    }
    return -1;
}

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

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:70:9: warning: unused variable 'ans' [-Wunused-variable]
   70 |     int ans=-1;
      |         ^~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27