oj.uz

답안 #81606

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81606 2018-10-25T14:47:27 Z ngot23 Mag (COCI16_mag) C++11
0 / 120
 2063 ms 263168 KB 
#include<bits/stdc++.h>
#define rep(i, a, b) for(long long i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const long long N=1000005;
vector <long long > g[N];
long long deg[N], n, a[N], h[N], par[N][22], topo[N], cnt;
long long b[N];

void DFS(long long u) {
    topo[++cnt]=u;
    for(long long 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);
    }
}

long long LCA(long long u, long long v) {
    if(h[u]<h[v]) swap(u, v);
    long long delta=h[u]-h[v];
    rep(i, 0, 19) {
        if((delta>>i)&1) u=par[u][i];
    }
    if(u==v) return u;
    for(long long 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) {
            long long 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];
            long long gcd=__gcd(T, num);
            T/=gcd, num/=gcd;
            if(P*num>T*Q) P=T, Q=num;
        }
    }
    cout << P << '/' << Q;
}

long long pointer;
vector<long long> M;
vector<long long> B;
bool bad(long long l1,long long l2,long long 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) {
        long long 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;
    long long mx=0;
    rep(i, 2, n) {
        long long 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&&
         ~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 105 ms 47996 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 48164 KB Output is correct
2 Incorrect 106 ms 48288 KB Output isn't correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 917 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.

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 24 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.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1087 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #6
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 742 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 692 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2063 ms 263168 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1769 ms 263168 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 731 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -