| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 165631 |
2019-11-27T21:38:39 Z |
sans |
Mag (COCI16_mag) |
C++14 |
|
1221 ms |
132160 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;
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
Compilation message
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){
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1067 ms |
132160 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 |
1044 ms |
109224 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1191 ms |
109536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
900 ms |
94832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
10992 KB |
Output is correct |
| 2 |
Incorrect |
1199 ms |
110144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
908 ms |
96612 KB |
Output is correct |
| 2 |
Incorrect |
1221 ms |
107628 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
971 ms |
110048 KB |
Output is correct |
| 2 |
Correct |
1117 ms |
55940 KB |
Output is correct |
