QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90540 | #5250. Combination Locks | SolitaryDream# | WA | 4ms | 9428kb | C++20 | 3.1kb | 2023-03-23 15:57:06 | 2023-03-23 15:57:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=1e5+50,M=1e7+50;
int Tr[M][2],mag[M],cnt[M],tol;
ll val[M];
int New(int v) {
int x=++tol;cnt[x]=1;
val[x]=v;mag[x]=rand();
return x;
}
void Up(int x) {
cnt[x]=cnt[Tr[x][0]]+cnt[Tr[x][1]]+1;
}
void rotate(int &x,int f) {
int y=Tr[x][f];
Tr[x][f]=Tr[y][!f];Tr[y][!f]=x;
Up(x);Up(y);x=y;
}
void Insert(int &x,ll v) {
if(!x) {x=New(v);return ;}
int f=v>val[x];
Insert(Tr[x][f],v);
if(mag[Tr[x][f]]>mag[x]) rotate(x,f);
Up(x);
}
int qry(int x,ll v) {
int t=0;
while(x) {
if(v<=val[x]) t+=cnt[Tr[x][1]]+1,x=Tr[x][0];
else x=Tr[x][1];
}
return t;
}
vector<pair<int,int>> E[N];
vector<pair<int,pair<int,ll>>> G[N];
bool mark[N];
int sz[N];
int Min,tot,rt;
int m;
void dfs1(int x,int fr) {
sz[x]=1;
for(auto [y,v]: E[x]) if(y!=fr && !mark[y]) {
dfs1(y,x);
sz[x]+=sz[y];
}
}
void dfs2(int x,int fr) {
int mx=tot-sz[x];
for(auto [y,v]: E[x]) if(y!=fr && !mark[y]) {
dfs2(y,x);
mx=max(mx,sz[y]);
}
if(mx<Min) Min=mx,rt=x;
}
void dfs3(int x,int fr,int c,ll d) {
G[x].push_back({rt,{c,d}});
for(auto [y,v]: E[x]) if(y!=fr && !mark[y]) {
dfs3(y,x,c,d+v);
}
}
void divide(int x) {
dfs1(x,0);
Min=tot=sz[x];
dfs2(x,0);
mark[rt]=1;
for(auto [y,v]: E[rt]) if(!mark[y]) {
dfs3(y,rt,++m,v);
}
for(auto [y,v]: E[rt]) if(!mark[y]) {
divide(y);
}
}
int root[M];
pair<int,int> ed[N];
int V[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin >> n;
FOR(i,2,n) {
int x,y,v;
cin >> x >> y >> v;
ed[i-1]={x,y};
V[i-1]=v;
E[x].push_back({y,v});
E[y].push_back({x,v});
}
m=n;
divide(1);
cin >> q;
while(q--) {
string s;
cin >> s;
if(s[0]=='+') {
int x;
ll r;
cin >> x >> r;
for(auto e: G[x]) {
int z=e.first;
auto [c,d]=e.second;
if(r>d) {
Insert(root[z],r-d);
Insert(root[c],r-d);
}
}
Insert(root[x],r);
} else {
int res=0;
int id;
cin >> id;
auto [x,y]=ed[id];
if(G[x].size()<G[y].size()) swap(x,y);
for(int i=0; i<G[y].size(); ++i) {
int z=G[y][i].first;
auto [c,d]=G[y][i].second;
d=max(d,G[x][i].second.second);
res+=qry(root[z],d)-qry(root[c],d);
}
for(int i=G[y].size(); i<G[x].size(); ++i) {
int z=G[x][i].first;
auto [c,d]=G[x][i].second;
if(y!=z) d+=V[id-1];
res+=qry(root[z],d)-qry(root[c],d);
}
cout << res << '\n';
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 9428kb
input:
2 1 0 0 0 1 1 0 0 .
output:
result:
wrong answer 1st lines differ - expected: 'Alice', found: ''