Submission #3909971
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
ll n,q,id[100005],k=1,w[100005],x[100005],y[100005],vis[100005];
set<P>m[100005];
set <P>g[100005];
int main(void){
scanf("%lld",&n);
for(int i=0;i<n-1;i++){
ll a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
a--,b--;
g[a].insert(P(b,i));
g[b].insert(P(a,i));
m[0].insert(P(c,i));
w[i]=c;
x[i]=a,y[i]=b;
}
scanf("%lld",&q);
while(q--){
ll t;
scanf("%lld",&t);
if(t==1){
ll e,d;
scanf("%lld%lld",&e,&d);
e--;
if(id[e]!=-1){
m[id[e]].erase(P(w[e],e));
w[e]+=d;
m[id[e]].insert(P(w[e],e));
}
}else{
ll e;
scanf("%lld",&e);
e--;
if(id[e]==-1){
printf("-1\n");
continue;
}
ll o=id[e];
e=m[o].begin()->S;
id[e]=-1;
printf("%lld\n",e+1);
m[o].erase(m[o].begin());
g[x[e]].erase(P(y[e],e));
g[y[e]].erase(P(x[e],e));
queue<ll>q[2];
vector<ll>p[2];
q[0].push(x[e]);
q[1].push(y[e]);
while(q[0].size()&&q[1].size()){
for(int i=0;i<2;i++){
ll v=q[i].front();
q[i].pop();
vis[v]=k;
for(auto it=g[v].begin();it!=g[v].end();it++){
if(vis[it->F]==k)continue;
q[i].push(it->F);
p[i].PB(it->S);
}
}
}
ll r=0;
if(q[1].empty())r=1;
for(int i=0;i<p[r].size();i++){
ll z=p[r][i];
m[id[z]].erase(P(w[z],z));
id[z]=k;
m[k].insert(P(w[z],z));
}
k++;
}
}
}
Submission Info
Submission Time |
|
Task |
I - 盆栽 |
User |
nxteru |
Language |
C++14 (GCC 5.4.1) |
Score |
30 |
Code Size |
1620 Byte |
Status |
TLE |
Exec Time |
5257 ms |
Memory |
33404 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:15:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
^
./Main.cpp:18:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&a,&b,&c);
^
./Main.cpp:26:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&q);
^
./Main.cpp:29:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&t);
^
./Main.cpp:32:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&e,&d);
^
./Main.cpp:...
Judge Result
Set Name |
Subtask |
All |
Score / Max Score |
30 / 30 |
0 / 270 |
Status |
|
|
Set Name |
Test Cases |
Subtask |
atetubou-challenge1.in, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt |
All |
scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt |
Case Name |
Status |
Exec Time |
Memory |
scrambled_00.txt |
AC |
6 ms |
12544 KB |
scrambled_01.txt |
AC |
7 ms |
12672 KB |
scrambled_02.txt |
AC |
7 ms |
12672 KB |
scrambled_03.txt |
AC |
7 ms |
12672 KB |
scrambled_04.txt |
AC |
7 ms |
12672 KB |
scrambled_05.txt |
AC |
7 ms |
12672 KB |
scrambled_06.txt |
AC |
7 ms |
12672 KB |
scrambled_07.txt |
AC |
7 ms |
12672 KB |
scrambled_08.txt |
AC |
7 ms |
12672 KB |
scrambled_09.txt |
AC |
7 ms |
12672 KB |
scrambled_10.txt |
AC |
7 ms |
12672 KB |
scrambled_11.txt |
AC |
352 ms |
32960 KB |
scrambled_12.txt |
AC |
356 ms |
32904 KB |
scrambled_13.txt |
AC |
359 ms |
32812 KB |
scrambled_14.txt |
AC |
368 ms |
32832 KB |
scrambled_15.txt |
AC |
397 ms |
32768 KB |
scrambled_16.txt |
AC |
346 ms |
32696 KB |
scrambled_17.txt |
AC |
382 ms |
32768 KB |
scrambled_18.txt |
AC |
408 ms |
32936 KB |
scrambled_19.txt |
AC |
392 ms |
32636 KB |
scrambled_20.txt |
AC |
390 ms |
32684 KB |
scrambled_21.txt |
TLE |
5257 ms |
33404 KB |
scrambled_22.txt |
AC |
8 ms |
12672 KB |
scrambled_23.txt |
AC |
8 ms |
12672 KB |
scrambled_24.txt |
AC |
7 ms |
12672 KB |
scrambled_25.txt |
AC |
7 ms |
12672 KB |
scrambled_26.txt |
AC |
8 ms |
12672 KB |
scrambled_27.txt |
AC |
340 ms |
32896 KB |
scrambled_28.txt |
AC |
349 ms |
32924 KB |
scrambled_29.txt |
AC |
353 ms |
32944 KB |
scrambled_30.txt |
AC |
349 ms |
32896 KB |
scrambled_31.txt |
AC |
339 ms |
32896 KB |
scrambled_32.txt |
AC |
6 ms |
12544 KB |
subtask_00.txt |
AC |
6 ms |
12544 KB |
subtask_01.txt |
AC |
7 ms |
12672 KB |
subtask_02.txt |
AC |
7 ms |
12672 KB |
subtask_03.txt |
AC |
7 ms |
12672 KB |
subtask_04.txt |
AC |
7 ms |
12672 KB |
subtask_05.txt |
AC |
7 ms |
12672 KB |
subtask_06.txt |
AC |
7 ms |
12672 KB |
subtask_07.txt |
AC |
7 ms |
12672 KB |
subtask_08.txt |
AC |
7 ms |
12672 KB |
subtask_09.txt |
AC |
7 ms |
12672 KB |
subtask_10.txt |
AC |
7 ms |
12672 KB |
subtask_11.txt |
AC |
7 ms |
12672 KB |
subtask_12.txt |
AC |
7 ms |
12672 KB |
subtask_13.txt |
AC |
7 ms |
12672 KB |
subtask_14.txt |
AC |
7 ms |
12672 KB |
subtask_15.txt |
AC |
7 ms |
12672 KB |
subtask_16.txt |
AC |
6 ms |
12544 KB |