#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e9+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;
ll n,m,q;
set<ll> *st[ARRS];
vector<ll> v[ARRS];
vector<ll> g[ARRS];
ll mn[ARRS];
ll mx[ARRS];
ll pr[ARRS];
void go(ll x,ll p){
pr[x]=p;
st[x]=new set<ll>;
for(auto y:g[x])
st[x]->insert(y);
//cout<<x<<endl;
for(auto y:v[x]){
if(y==p)continue;
go(y,x);
if(st[x]->size()<st[y]->size())swap(st[x],st[y]);
for(auto k:*st[y]){
if(st[x]->find(k)!=st[x]->end())
st[x]->erase(k);
else st[x]->insert(k);
}
}
st[x]->insert(0);
st[x]->insert(MAX);
mx[x]=*st[x]->upper_bound(0);
mn[x]=-(*st[x]->begin());
//mx[x]=max(-1ll,mx[x]);
if(mx[x]==MAX)mx[x]=0;
}
ll f[ARRS];
ll pas[ARRS];
map<ll,ll> mp;
bool mv(ll x){
if(x==-1)return 0;
if(!x)return 1;
if(f[x])return 0;
else if(mx[x]&&mv(mp[mx[x]])){
mp[mx[x]]=x;
return 1;
}
else return 0;
}
int main(){
#ifdef KHOKHO
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif // KHOKHO
ios::sync_with_stdio(0);
cin>>n;
for(int i=0; i<n-1; i++){
ll k,p;
cin>>k>>p;
v[k].pb(p);
v[p].pb(k);
}
cin>>q;
for(int i=0; i<q; i++){
char ch;
ll x,y,k;
cin>>ch>>x>>y>>k;
k++;
if(ch=='m'){
g[x].pb(-k);
g[y].pb(-k);
}
else {
g[x].pb(k);
g[y].pb(k);
}
}
go(1,-1);
mp[0]=-1;
for(int i=2; i<=n; i++){
ll x=i;
if(mn[x]&&mv(mp[mn[x]])){
mp[mn[x]]=x;
}
else if(mx[x]&&mv(mp[mx[x]])){
f[x]=1;
mp[mx[x]]=x;
}
}
for(auto x:mp)
pas[mp[x.fr]]=x.fr;
for(int i=2; i<=n; i++){
if(!pas[i])pas[i]=mn[i];
cout<<pr[i]<<" "<<i<<" "<<pas[i]-1<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
94328 KB |
Output is correct |
| 2 |
Correct |
86 ms |
94500 KB |
Output is correct |
| 3 |
Correct |
82 ms |
94500 KB |
Output is correct |
| 4 |
Runtime error |
553 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
510 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
699 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
94328 KB |
Output is correct |
| 2 |
Correct |
86 ms |
94500 KB |
Output is correct |
| 3 |
Correct |
82 ms |
94500 KB |
Output is correct |
| 4 |
Runtime error |
553 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
