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

Submission #3910096

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();
					vis[v]=k;
					if(it==g[v].end())continue;
					p[i].PB(it->S);
					if(vis[it->F]!=k){
						q[i].push(MP(it->F,g[it->F].begin()));
					}
					it++;
					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状態 AC
Score得点 300
Source lengthソースコード長 1768 Byte
File nameファイル名
Exec time実行時間 484 ms
Memory usageメモリ使用量 34864 KB

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 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 270 / 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 8 ms 12672 KB
scrambled_02.txt AC 8 ms 12672 KB
scrambled_03.txt AC 7 ms 12672 KB
scrambled_04.txt AC 8 ms 12672 KB
scrambled_05.txt AC 7 ms 12672 KB
scrambled_06.txt AC 8 ms 12800 KB
scrambled_07.txt AC 7 ms 12672 KB
scrambled_08.txt AC 7 ms 12672 KB
scrambled_09.txt AC 8 ms 12800 KB
scrambled_10.txt AC 8 ms 12672 KB
scrambled_11.txt AC 456 ms 33376 KB
scrambled_12.txt AC 468 ms 33364 KB
scrambled_13.txt AC 475 ms 33052 KB
scrambled_14.txt AC 447 ms 33240 KB
scrambled_15.txt AC 476 ms 34864 KB
scrambled_16.txt AC 446 ms 32712 KB
scrambled_17.txt AC 439 ms 32984 KB
scrambled_18.txt AC 481 ms 33492 KB
scrambled_19.txt AC 441 ms 32824 KB
scrambled_20.txt AC 434 ms 32716 KB
scrambled_21.txt AC 178 ms 32896 KB
scrambled_22.txt AC 8 ms 12800 KB
scrambled_23.txt AC 8 ms 12800 KB
scrambled_24.txt AC 8 ms 12672 KB
scrambled_25.txt AC 8 ms 12672 KB
scrambled_26.txt AC 8 ms 12672 KB
scrambled_27.txt AC 457 ms 32896 KB
scrambled_28.txt AC 456 ms 33008 KB
scrambled_29.txt AC 483 ms 33004 KB
scrambled_30.txt AC 484 ms 33072 KB
scrambled_31.txt AC 455 ms 32896 KB
scrambled_32.txt AC 6 ms 12544 KB
subtask_00.txt AC 6 ms 12544 KB
subtask_01.txt AC 8 ms 12672 KB
subtask_02.txt AC 7 ms 12672 KB
subtask_03.txt AC 7 ms 12672 KB
subtask_04.txt AC 8 ms 12800 KB
subtask_05.txt AC 7 ms 12672 KB
subtask_06.txt AC 8 ms 12800 KB
subtask_07.txt AC 8 ms 12672 KB
subtask_08.txt AC 8 ms 12672 KB
subtask_09.txt AC 8 ms 12800 KB
subtask_10.txt AC 8 ms 12672 KB
subtask_11.txt AC 8 ms 12672 KB
subtask_12.txt AC 8 ms 12672 KB
subtask_13.txt AC 8 ms 12672 KB
subtask_14.txt AC 8 ms 12672 KB
subtask_15.txt AC 8 ms 12672 KB
subtask_16.txt AC 6 ms 12544 KB