東京大学プログラミングコンテスト2014

Submission #3909971

Source codeソースコード

#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

Task問題 I - 盆栽
User nameユーザ名 nxteru
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 TLE
Score得点 30
Source lengthソースコード長 1620 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./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:...

Test case

Set

Set name Score得点 / Max score Cases
Subtask 30 / 30 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 0 / 270 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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
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