Submission #943906

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
943906	2024-03-12T04:17:46 Z	vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	408 ms	29268 KB

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--;
			last = res + it ->ff;
			cout << res + it ->ff << endl;
		}else{
			cout << res << endl;
			last = res;
		}
	}
}	
/*
 * 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

diameter.cpp:39:1: 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:29: 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:70: 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.0

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

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4952 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	1 ms	4952 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	4 ms	4956 KB	Output is correct
4	Correct	32 ms	5216 KB	Output is correct
5	Correct	157 ms	5488 KB	Output is correct
6	Correct	1 ms	5208 KB	Output is correct
7	Correct	2 ms	5212 KB	Output is correct
8	Correct	2 ms	5212 KB	Output is correct
9	Correct	5 ms	5212 KB	Output is correct
10	Correct	35 ms	5212 KB	Output is correct
11	Correct	166 ms	5668 KB	Output is correct
12	Correct	4 ms	5980 KB	Output is correct
13	Correct	4 ms	5980 KB	Output is correct
14	Correct	8 ms	5980 KB	Output is correct
15	Correct	40 ms	6248 KB	Output is correct
16	Correct	181 ms	6996 KB	Output is correct
17	Correct	96 ms	27372 KB	Output is correct
18	Correct	92 ms	27272 KB	Output is correct
19	Correct	92 ms	27472 KB	Output is correct
20	Correct	137 ms	27776 KB	Output is correct
21	Correct	408 ms	29268 KB	Output is correct