| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 81603 |
2018-10-25T14:44:10 Z |
ngot23 |
Mag (COCI16_mag) |
C++11 |
|
4000 ms |
263168 KB |
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=1000005;
vector <int > g[N];
int deg[N], n, a[N], h[N], par[N][22], topo[N], cnt;
long long b[N];
void DFS(int u) {
topo[++cnt]=u;
for(int v:g[u]) {
if(v==par[u][0]) continue;
h[v]=h[u]+1;
b[v]*=b[u];
par[v][0]=u;
rep(i, 1, 19) par[v][i]=par[par[v][i-1]][i-1];
DFS(v);
}
}
int LCA(int u, int v) {
if(h[u]<h[v]) swap(u, v);
int delta=h[u]-h[v];
rep(i, 0, 19) {
if((delta>>i)&1) u=par[u][i];
}
if(u==v) return u;
for(int i=19 ; i>=0 ; --i) {
if(par[u][i]!=par[v][i]) u=par[u][i], v=par[u][i];
}
return par[u][0];
}
void sub1() {
long long P=5e18, Q=1;
rep(i, 1, n) {
if(P>1ll*a[i]*Q) P=a[i], Q=1;
rep(j, i+1, n) {
int cha=LCA(i, j);
long long num=h[i]+h[j]-h[cha]*2+1;
long long T=(b[i]/b[cha])*(b[j]/b[cha])*a[cha];
int gcd=__gcd(T, num);
T/=gcd, num/=gcd;
if(P*num>T*Q) P=T, Q=num;
}
}
cout << P << '/' << Q;
}
int pointer;
vector<long long> M;
vector<long long> B;
bool bad(int l1,int l2,int l3)
{
return (B[l3]-B[l1])*(M[l1]-M[l2])<=(B[l2]-B[l1])*(M[l1]-M[l3]);
}
void add(long long m,long long b)
{
M.push_back(m);
B.push_back(b);
while (M.size()>=3&&bad(M.size()-3,M.size()-2,M.size()-1))
{
M.erase(M.end()-2);
B.erase(B.end()-2);
}
}
long long query(long long x)
{
if (pointer>=M.size())
pointer=M.size()-1;
while (pointer<M.size()-1&&
M[pointer+1]*x+B[pointer+1]>M[pointer]*x+B[pointer])
pointer++;
return M[pointer]*x+B[pointer];
}
void sub2() {
long long P=5e18, Q=1;
add(1, 0);
b[0]=1;
rep(i, 1, n) {
int u=topo[i];
long long M=query(i);
long long gcd=__gcd(M, b[u]);
long long T=b[u]/gcd;
M/=gcd;
if(P*M>Q*T) P=T, Q=M;
add(b[u], -1ll*i*b[u]);
}
cout << P << '/' << Q;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen(Task".inp", "r", stdin);
//freopen(Task".out", "w", stdout);
cin >> n;
int mx=0;
rep(i, 2, n) {
int u, v;
cin >> u >> v;
++deg[u], ++deg[v];
g[u].push_back(v);
g[v].push_back(u);
}
rep(i, 1, n) {
cin >> a[i], b[i]=a[i];
mx=max(mx, deg[i]);
}
DFS(1);
if(mx<=2) sub2();
else sub1();
return 0;
}
Compilation message
mag.cpp: In function 'long long int query(long long int)':
mag.cpp:72:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pointer>=M.size())
~~~~~~~^~~~~~~~~~
mag.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (pointer<M.size()-1&&
~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 ms |
47824 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
47980 KB |
Output is correct |
| 2 |
Incorrect |
129 ms |
48160 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
691 ms |
193320 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
193320 KB |
Output is correct |
| 2 |
Runtime error |
1146 ms |
263168 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
926 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1601 ms |
263168 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
263168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1869 ms |
263168 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1345 ms |
263168 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4016 ms |
263168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
