제출 #984583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
984583		Mr_Ph	자매 도시 (APIO20_swap)	C++17	37 / 100	2059 ms	23720 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
// #include "grader.cpp"
using namespace std;
vector<vector<pair<int,int>>>adj;
int mx=0,n=0;
void init(int N, int m,std::vector<int> u, std::vector<int> v, std::vector<int> w) {
    adj.resize(N+1);
    for(int i=0;i<m;i++)
    {
        adj[u[i]].push_back({v[i],w[i]});
        adj[v[i]].push_back({u[i],w[i]});
        mx=max(mx,w[i]);
    }
    n=N;
}
vector<vector<int>>newadj;
vector<int>vs;
bool check(int node,int parent)
{
    // cout<<node<<" "<<parent<<endl;
    int cnt=0;
    if(vs[node]==true)return 1;
    vs[node]=true;
    for(auto i:newadj[node])
    {
        if(i==parent)continue;
        cnt++;
    }
    if(cnt>1&&parent!=-1)return 1;
    else
    {
        int lol=0;
        for(auto i:newadj[node])
        {
            if(i==parent)continue;
            lol|=check(i,node);
        }
        return lol;
    }
}
bool findy(int node,int y)
{
    vs[node]=true;
    if(node==y)return 1;
    int lol=0;
    for(auto i:newadj[node])
    {
        if(!vs[i])
            lol|=findy(i,y);
    }
    return lol;
}
int getMinimumFuelCapacity(int x, int y) {
    int l=1,r=mx;
    int ans=-1;
    newadj.resize(n+1);
    vs.resize(n+1);
    for(int i=0;i<=n;i++)vs[i]=0;
    while(l<=r){
        int mid=(l+r)/2;
        for(int i=0;i<n;i++)
            for(auto j:adj[i])
                if(j.second<=mid)
                    newadj[i].push_back(j.first);
        int node=-1;
        // cout<<"HI"<<endl;
        int e=check(x,-1);
        for(int i=0;i<n;i++)vs[i]=0;
        int ee=findy(x,y);
        if(e&&ee)
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
        for(int i=0;i<n;i++)
        {
            vs[i]=0;
            newadj[i].clear();
        }
    }
    return ans;
}

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

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:67:13: warning: unused variable 'node' [-Wunused-variable]
   67 |         int node=-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