Submission #165627

#	Time	Username	Problem	Language	Result	Execution time	Memory
165627		sans	Mag (COCI16_mag)	C++14	24 / 120	550 ms	94596 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;
vector<vector<int>> AdjList;
vector<bool> visited;
int N;

map<int, int> birnodeno;
int maxy = 1;

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));
    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(birNodes.empty() == false) birvar = true;
    
    if(!birvar){ cout << miny << "/1" << endl; return 0; }

    for(int i = 0; i < birNodes.size(); ++i){
        enuzunbiryol(birNodes[i]);
    }
    cout << "1/" << maxy << endl;

    return 0;
}

//cikisir

Compilation message (stderr)

mag.cpp: In function 'int main(int, char**)':
mag.cpp:113: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