Submission #276007

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
276007	2020-08-20T09:21:19 Z	Fasho	Dynamic Diameter (CEOI19_diameter)	C++14	7 / 100	594 ms	14432 KB

diameter

#include <bits/stdc++.h>
#define N 100005
#define ll long long int
#define fo(i,x,y)	for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define mod 1000000007
using namespace std;

ll n,m,ar[N],sum,t,mki1,mki2,mk,mk1,mk2;

pair<lli,ll> p[N];
multiset<ll> st;
vector<int> v[N];

void f(int ind,int back,int dist)
{
	if(dist>mk)
	{
		mk=dist,
		mki1=ind;
	}
	for(int i=0;i<v[ind].size();i++)
	{
		ll x=p[v[ind][i]].fi.fi;
		if(x==ind)
			x=p[v[ind][i]].fi.se;
		ll y=p[v[ind][i]].se;
		if(x==back)
			continue;
		f(x,ind,dist+y);
	}
}
ll calc()
{
	mk=0;
	f(1,1,0);
	swap(mki1,mki2);
	mk=0;
	f(mki2,mki2,0);
	return mk;
}

int main()
{
	fast;
	ll bos;
	cin>>n>>m>>bos;
	fo(i,1,n-1)
	{
		ll a,b,c;
		cin>>a>>b>>c;
		v[a].pb(i);
		v[b].pb(i);
		p[i]={{a,b},c};
			st.insert(c);
		if(mki2!=i)
		{
			if(mk2<c)
				mk2=c,mki2=i;
		}
		if(mk1<mk2)
		{
			swap(mki1,mki2);
			swap(mk1,mk2);
		}
	}
	ll last=0;
	// cout<<st.size()<<endl;
	fo(i,1,m)
	{
		ll x, y;
		cin>>x>>y;
		if(i!=1)
		{
			x=(x+last)%(n-1);
			y=(y+last)%bos;
		}
		ll tt=p[x+1].se;
		auto it=st.find(tt);
		st.erase(it);
		st.insert(y);
		p[x+1].se=y;
		it=st.end();
		it--;
		ll a=*it;
		if(st.size()==1)
		{
			last=a;
			cout<<last<<endl;
			continue;
		}
		st.erase(it);
		it=st.end();
		it--;
		ll b=*it;

		last=a+b;
		// cout<<"[ans]"<<endl;
		// cerr<<a<<sp<<b<<endl;
		cout<<last<<endl;
		st.insert(a);
		// cerr<<"[d]"<<endl;
	}


}

Compilation message

diameter.cpp: In function 'void f(int, int, int)':
diameter.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	2688 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	2688 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	3 ms	2688 KB	Output is correct
3	Correct	9 ms	2688 KB	Output is correct
4	Correct	61 ms	2760 KB	Output is correct
5	Correct	270 ms	3192 KB	Output is correct
6	Correct	3 ms	2688 KB	Output is correct
7	Correct	3 ms	2688 KB	Output is correct
8	Correct	3 ms	2688 KB	Output is correct
9	Correct	8 ms	2816 KB	Output is correct
10	Correct	58 ms	2816 KB	Output is correct
11	Correct	284 ms	3192 KB	Output is correct
12	Correct	6 ms	3200 KB	Output is correct
13	Correct	8 ms	3200 KB	Output is correct
14	Correct	12 ms	3328 KB	Output is correct
15	Correct	79 ms	3320 KB	Output is correct
16	Correct	338 ms	3728 KB	Output is correct
17	Correct	83 ms	13296 KB	Output is correct
18	Correct	105 ms	13296 KB	Output is correct
19	Correct	102 ms	13292 KB	Output is correct
20	Correct	176 ms	13424 KB	Output is correct
21	Correct	560 ms	13872 KB	Output is correct