제출 #165631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
165631		sans	Mag (COCI16_mag)	C++14	24 / 120	1221 ms	132160 KiB

mag

#include <iostream>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

#define sp ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << endl
#define prs(XX) cout << XX << " "

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;
const int mINF = -2e9 - 13;
const double PI = 3.14159265358979;
const double EPS = 1e-9;

class UnionFind{
    private:
        vector<int> p, rank, setSize;
        int numSets;
    public:
        UnionFind(int N){
            rank.assign(N, 0); setSize.assign(N, 1); numSets = N;
            p.resize(N); for(int i = 0; i < N; ++i) p[i] = i;
        }

        int findSet(int i){ return p[i] == i ? i : p[i] = findSet(p[i]); }
        bool isSameSet(int i, int j){ return (findSet(i) == findSet(j)); }

        void unionSet(int i, int j){
            if(!isSameSet(i, j)){
                numSets--;
                int x = findSet(i), y = findSet(j);

                if(rank[x] > rank[y]){
                    p[y] = x; setSize[x] += setSize[y];
                }
                else{
                    p[x] = y; setSize[y] += setSize[x];
                    if(rank[x] == rank[y]) rank[y]++;
                }
            }
        }

        int numDisjointSets(void){ return numSets; }
        int sizeOfSet(int i){ return setSize[findSet(i)]; }

};

vector<int> birNodes, X, ikiNodes;
vector<vector<int>> AdjList;
vector<bool> visited;
int N;

int maxy = 1;

bool ikikabul = false;
map<int, int> enuzunnodedan;

int enuzunbiryol(int n){
    if(visited[n]) return 0;

    visited[n] = true;
    vector<int> yollar;

    for(int i = 0; i < (int)AdjList[n].size(); ++i){
        int v = AdjList[n][i];
        if(X[v] == 1 and !visited[v])
            yollar.pb( enuzunbiryol(v) + 1 );
    }
    //cout << n << sp << (yollar.empty() ? sp : yollar[0]) << endl;
    if(!yollar.empty()) sort(yollar.rbegin(), yollar.rend());
    if(yollar.size() > 1) maxy = max(maxy, yollar[0] + yollar[1] - 1);
    else maxy = max(maxy, (!yollar.empty() ? yollar[0] : 1));

    enuzunnodedan[n] = (yollar.empty() ? 1 : yollar[0]);
    return (yollar.empty() ? 1 : yollar[0]);
}

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    AdjList.resize(N);
    X.resize(N); visited.assign(N, false);

    for(int i = 0; i < N-1; ++i){
        int u, v; cin >> u >> v; u--; v--;
        AdjList[u].pb(v);
        AdjList[v].pb(u);
    }

    int miny = INF;
    bool birvar = false;
    for(int i = 0; i < N; ++i){
        cin >> X[i]; miny = min(miny, X[i]);
        if(X[i] == 1) birNodes.pb(i);
        if(X[i] == 2) ikiNodes.pb(i);
    }
    if(birNodes.empty() == false) birvar = true;

    pair<double, pair<int, int>> ans = mp(INF, mp(-1, -1));
    
    if(!birvar){ cout << miny << "/1" << endl; return 0; }

    for(int i = 0; i < ikiNodes.size(); ++i){
        int u = ikiNodes[i]; int enuzun1 = -1, enuzun2 = -1;
        
        for(int j = 0; j < (int)AdjList[u].size(); ++j){
            int v = AdjList[u][j];
            if(X[v] == 1){
                int pathlen = enuzunbiryol(v);
                if(pathlen > enuzun1){
                    enuzun2 = enuzun1;
                    enuzun1 = pathlen;
                }
                else if(pathlen > enuzun2){
                    enuzun2 = pathlen;
                }
            }
        }
        if(enuzun1 == 1 or enuzun2 == 1) continue;

        if(enuzun1 > 0 and enuzun2 > 0){
            int tot = enuzun1 + enuzun2 + 1;
            
            if(((double)2/(double)tot) < ans.st){
                ans.st = (double)2/(double)tot;
                if(tot%2) ans.nd.st = 2, ans.nd.nd = tot;
                else ans.nd.st = 1, ans.nd.nd = tot/2;
            }
        }
    }

    visited.assign(N, false);
    for(int i = 0; i < birNodes.size(); ++i){
        enuzunbiryol(birNodes[i]);
    }
    if( ((double)1/(double)maxy) < ans.st ){
        ans.st = ((double)1/(double)maxy);
        ans.nd.st = 1;
        ans.nd.nd = maxy;
    }

    cout << ans.nd.st << "/" << ans.nd.nd << endl;

    return 0;
}

//cikisir

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

mag.cpp: In function 'int main(int, char**)':
mag.cpp:120:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ikiNodes.size(); ++i){
                    ~~^~~~~~~~~~~~~~~~~
mag.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < birNodes.size(); ++i){
                    ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 12 / 12