Submission #943904

#	Time	Username	Problem	Language	Result	Execution time	Memory
943904		vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	422 ms	27728 KiB

diameter

	#pragma GCC optimize("Ofast,unroll-loops")
	#pragma GCC target("avx,avx2,fma")
	#include <bits/stdc++.h>
	 
	#define ff first
	#define ss second
	#define pb push_back
	#define all(x) x.begin(),x.end()
	#define rall(x) x.rbegin(),x.rend()
	#define int long long
	#define rnd(l, r) uniform_int_distribution<int>(l, r)(rng)
	 
	using namespace std;
	 
	void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);} 
	int pow(int a,int b,int m){int ans=1;while(b){if(b&1){ans=(ans*a)%m;}b>>=1;a=(a*a)%m;}return ans;}
	int binpow(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a);}b>>=1;a=(a*a);}return ans;}
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	 
	const int N = 1e5 + 100, mxc = 105, inf = 1e18, MX = 1e5 + 10;

	set <pair <int,int> > g[N];

	int res=0,mx=0,va;
	void dfs(int v,int par = -1,int dis = 0){
		//cout << v <<"-"<< dis << endl;
		if(dis>mx){
			mx=dis;
			va=v;
		}
		for(auto to:g[v]){
			if(to.ss==par){
				continue;
			}
			dfs(to.ss,v,dis+to.ff);
		}
	}

	main(){
		iostream::sync_with_stdio	(false);	
		cin.tie(nullptr);
		cout.tie(nullptr);
		int n, q, W;
		cin >> n >> q >> W;
		vector <array<int, 3> > vp(n);
		set <pair <int,int> > st;
		for(int i = 0; i < n - 1; i++){
			int a, b, c;
			cin >> a >> b >> c;
			g[a].insert({c, b});
			g[b].insert({c, a});
			st.insert({c, b});
			vp[i] = {a, b, c};
		}
		int last = 0;
		while(q--){
			int d, e;
			cin >> d >> e;
			d = (d + last) % (n - 1);
			e = (e + last) % W;
			auto &[a, b, c] = vp[d];
			if(b == 1)
				swap(a, b);
			g[a].erase({c, b});
			g[b].erase({c, a});
			st.erase({c, b});
			g[a].insert({e, b});
			g[b].insert({e, a});
			vp[d][2] = e;
			st.insert({e, b});
			auto it = --st.end();
			int res = it ->ff;
			if(it != st.begin()){
				it--;
				cout << res + it ->ff << endl;
			}else
				cout << res << endl;
		}
	}	
	/*
	 * Before implementing the problem:
		
		Do I understand the problem correctly?
		Which places are tricky? What do I need to remember to implement them correctly?
		Which place is the heaviest by implementation? Can I do it simpler?
		Which place is the slowest? Where do I need to be careful about constant factors and where I can choose slower but simpler implementation?
		----------------------------------
		If not AC:
	 
		Did you remember to do everything to handle the tricky places you thought about before?
		Is the solution correct?
		Do I understand the problem correctly?
		----------------------------------
		If you have a test on which the solution gives wrong answer:
	 
		Is the solution doing what it was supposed to do?
		Is the problem in the code or in the idea?
	*/

Compilation message (stderr)

diameter.cpp:39:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 |  main(){
      |  ^~~~
diameter.cpp: In function 'void fp(std::string)':
diameter.cpp:15:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:15:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27