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

Submission #3910068

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
#define MP make_pair
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<pair<ll,set<P>::iterator>>q[2];
			vector<ll>p[2];
			q[0].push(MP(x[e],g[x[e]].begin()));
			q[1].push(MP(y[e],g[y[e]].begin()));
			while(q[0].size()&&q[1].size()){
				for(int i=0;i<2;i++){
					ll v=q[i].front().F;
					auto it=q[i].front().S;
					q[i].pop();
					p[i].PB(it->S);
					vis[v]=k;
					if(vis[it->F]!=k){
						q[i].push(MP(it->F,g[it->F].begin()));
					}
					it++;
					if(it!=g[v].end())q[i].push(MP(v,it));
				}
			}
			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得点 0
Source lengthソースコード長 1752 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:16:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
^
./Main.cpp:19: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:27:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&q);
^
./Main.cpp:30:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&t);
^
./Main.cpp:33: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 0 / 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 TLE
scrambled_01.txt TLE
scrambled_02.txt TLE
scrambled_03.txt TLE
scrambled_04.txt TLE
scrambled_05.txt TLE
scrambled_06.txt TLE
scrambled_07.txt TLE
scrambled_08.txt TLE
scrambled_09.txt TLE
scrambled_10.txt TLE
scrambled_11.txt TLE
scrambled_12.txt TLE
scrambled_13.txt TLE
scrambled_14.txt TLE
scrambled_15.txt TLE
scrambled_16.txt TLE
scrambled_17.txt TLE
scrambled_18.txt TLE
scrambled_19.txt TLE
scrambled_20.txt TLE
scrambled_21.txt TLE
scrambled_22.txt TLE
scrambled_23.txt TLE
scrambled_24.txt TLE
scrambled_25.txt TLE
scrambled_26.txt TLE
scrambled_27.txt TLE
scrambled_28.txt TLE
scrambled_29.txt TLE
scrambled_30.txt TLE
scrambled_31.txt TLE
scrambled_32.txt TLE
subtask_00.txt TLE
subtask_01.txt TLE
subtask_02.txt TLE
subtask_03.txt TLE
subtask_04.txt TLE
subtask_05.txt TLE
subtask_06.txt TLE
subtask_07.txt TLE
subtask_08.txt TLE
subtask_09.txt TLE
subtask_10.txt TLE
subtask_11.txt TLE
subtask_12.txt TLE
subtask_13.txt TLE
subtask_14.txt TLE
subtask_15.txt TLE
subtask_16.txt TLE