| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 165630 |
2019-11-27T21:31:49 Z |
sans |
Mag (COCI16_mag) |
C++14 |
|
1039 ms |
132116 KB |
#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;
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;
}
}
}
//cout << enuzun1 << sp << enuzun2 << endl;
if(enuzun1 == 1 or enuzun2 == 1) break;
if(enuzun1 > 0 and enuzun2 > 0){
int tot = enuzun1 + enuzun2 + 1;
if(tot % 2){ cout << "2/" << tot << endl; return 0; }
else{ cout << "1/" << tot/2 << endl; return 0; }
}
}
visited.assign(N, false);
for(int i = 0; i < birNodes.size(); ++i){
enuzunbiryol(birNodes[i]);
}
cout << "1/" << maxy << endl;
return 0;
}
//cikisir
Compilation message
mag.cpp: In function 'int main(int, char**)':
mag.cpp:118:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ikiNodes.size(); ++i){
~~^~~~~~~~~~~~~~~~~
mag.cpp:145:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < birNodes.size(); ++i){
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1039 ms |
132116 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
461 ms |
65312 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
769 ms |
109408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
701 ms |
94940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
7000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
701 ms |
96596 KB |
Output is correct |
| 2 |
Incorrect |
910 ms |
107520 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
964 ms |
109908 KB |
Output is correct |
| 2 |
Incorrect |
773 ms |
55848 KB |
Output isn't correct |
