QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#167353 | #6738. Cover | PhantomThreshold | WA | 864ms | 142988kb | C++20 | 3.6kb | 2023-09-07 14:03:27 | 2023-09-07 14:03:27 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxn = 100005;
const int maxm = 500005;
const int maxd = 18;
const int mask = 1<<11;
inline void up(int &a,const int &b){ if(a<b)a=b; }
int n,m,K;
vector<int>V[maxn];
int fa[maxn][maxd],dep[maxn],d[maxn];
void dfs(const int x)
{
for(int i=1;i<maxd;i++) fa[x][i]=fa[ fa[x][i-1] ][i-1];
for(auto y:V[x]) if(y!=fa[x][0])
{
d[x]++;
dep[y]=dep[x]+1;
fa[y][0]=x;
dfs(y);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=maxd-1;i>=0;i--) if(dep[x]-dep[y]>=(1<<i))
x=fa[x][i];
if(x==y) return x;
for(int i=maxd-1;i>=0;i--) if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int kthfa(int x,int k)
{
for(int i=maxd-1;i>=0;i--) if(k>=(1<<i))
x=fa[x][i];
return x;
}
int ty[maxm],ec[maxm];
vector<int>pr[maxm];
vector<int>Va[maxn],Vb[maxn];
int cnt,val[maxm<<1];
vector< int >S[maxn]; int flag[maxn];
int yid[20],yy[maxn];
int f[mask],g[maxn];
int ad1[20],ad2[20][20];
void dp(const int x)
{
for(auto y:V[x]) if(y!=fa[x][0])
dp(y);
{
int idx=0;
for(auto y:V[x]) if(y!=fa[x][0])
{
yid[idx]= y;
yy[y]=idx;
idx++;
}
}
for(int i=0;i<d[x];i++)
{
ad1[i]=0;
for(int j=0;j<d[x];j++)
ad2[i][j]=0;
}
for(auto i:Vb[x])
{
if(pr[i].size()==1)
{
int u=pr[i][0], ui=yy[u];
up( ad1[ui], ec[i] + val[i<<1]+flag[u] );
}
else
{
int u=pr[i][0], ui=yy[u];
int v=pr[i][1], vi=yy[v];
up( ad2[ui][vi], ec[i] + val[i<<1]+flag[u] + val[i<<1|1]+flag[v] );
up( ad2[vi][ui], ec[i] + val[i<<1]+flag[u] + val[i<<1|1]+flag[v] );
}
}
for(int i=0;i<d[x];i++)
{
up( ad1[i], g[yid[i]] );
}
memset(f,0,sizeof f);
int uS = 1<<d[x];
//f[x][0]=0;
for(int s=1;s<uS;s++)
{
int yi=31-__builtin_clz(s);
up(f[s], f[s^(1<<yi)]+ad1[yi]);
for(int j=0;j<yi;j++) if(s>>j&1)
{
up(f[s], f[s^1<<yi^1<<j]+ad2[yi][j]);
}
/* for(auto i:Vb[x])
{
if(pr[i].size()==1)
{
int u=pr[i][0], ui=yy[u];
if(s>>ui&1)
up(f[s], f[s^1<<ui]+);
}
else
{
int u=pr[i][0], ui=yy[u];
int v=pr[i][1], vi=yy[v];
if( (s>>ui&1) && (s>>vi&1) )
up(f[s], f[s^1<<ui^1<<vi]+ec[i] + val[i<<1]+flag[u] + val[i<<1|1]+flag[v]);
}
}*/
}
int idx=0;
for(auto y:V[x]) if(y!=fa[x][0])
{
flag[y]+= f[(uS-1)^1<<idx];
if( S[x].size()<S[y].size() )
swap(S[x],S[y]),swap(flag[x],flag[y]);
for(auto i:S[y])
{
val[i]+= flag[y]-flag[x];
S[x].push_back( i );
}
idx++;
}
g[x]=f[uS-1];
for(auto i:Va[x])
{
val[i]= g[x]-flag[x];
S[x].push_back( i );
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>K;
for(int i=1;i<n;i++)
{
int x,y; cin>>x>>y;
V[x].push_back(y);
V[y].push_back(x);
}
dep[1]=1; dfs(1);
for(int i=1;i<=m;i++)
{
int ai,bi,wi; cin>>ai>>bi>>wi;
ec[i]=wi;
int ff=lca(ai,bi);
if(ff==ai || ff==bi)
{
ty[i]=1;
Vb[ff].push_back(i);
if(ai!=ff)
{
Va[ai].push_back(i<<1);
pr[i].push_back(kthfa(ai,dep[ai]-dep[ff]-1));
}
else
{
Va[bi].push_back(i<<1);
pr[i].push_back(kthfa(bi,dep[bi]-dep[ff]-1));
}
}
else
{
ty[i]=2;
Vb[ff].push_back(i);
Va[ai].push_back(i<<1);
pr[i].push_back(kthfa(ai,dep[ai]-dep[ff]-1));
Va[bi].push_back(i<<1|1);
pr[i].push_back(kthfa(bi,dep[bi]-dep[ff]-1));
}
}
dp(1);
cout<<g[1]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 35140kb
input:
5 7 3 1 2 1 3 2 4 2 5 3 2 8 5 4 10 3 1 2 1 2 7 2 1 2 1 2 1 5 2 3
output:
19
result:
ok 1 number(s): "19"
Test #2:
score: -100
Wrong Answer
time: 864ms
memory: 142988kb
input:
100000 500000 12 2 1 3 2 4 2 5 2 6 5 7 2 8 5 9 3 10 2 11 2 12 5 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 12 25 2 26 2 27 2 28 2 29 2 30 15 31 30 32 23 33 26 34 22 35 30 36 26 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 20 48 21 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 5...
output:
491616561283
result:
wrong answer 1st numbers differ - expected: '660925834533', found: '491616561283'