제출 #1156655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156655		8pete8	Grapevine (NOI22_grapevine)	C++20	100 / 100	773 ms	51360 KiB

Main

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<complex>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
using namespace std;
using cd = complex<double>;
double const PI=acos(-1);
const int mod=1e9+7,mxn=1e5+5,inf=1e18,minf=-1e18,lg=27,Mxn=lg*mxn;
//#undef int
int k,m,n,q,d;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);	
	freopen((name+".out").c_str(),"w",stdout);	
}
//centroid decomp??
int W[mxn+10],ans[mxn+10],CW[mxn+10],yes[mxn+10];
vector<pii>adj[mxn+10],edge_update[mxn+10];
vector<int>node_update[mxn+10],node_qry[mxn+10];
pii E[mxn+10];
int del[mxn+10],sz[mxn+10];
void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i.f!=p&&!del[i.f])getsz(i.f,cur),sz[cur]+=sz[i.f];}
int getcen(int cur,int p,int need){
	for(auto i:adj[cur])if(i.f!=p&&!del[i.f]){
		if(sz[i.f]>need)return getcen(i.f,cur,need);
	}
	return cur;
}
struct seg{
	int lazy[4*mxn+10],val[4*mxn+10],cnt[4*mxn+10],mn[4*mxn+10];
	void init(int n){for(int i=0;i<=4*n;i++)mn[i]=inf,val[i]=cnt[i]=lazy[i]=0;}
	void apply(int pos,int l,int r,int x){
		lazy[pos]+=x;
		val[pos]+=x;
		if(mn[pos]!=inf)mn[pos]+=x;
	}
	void push(int pos,int l,int r){
		if(l!=r){
			int mid=l+(r-l)/2;
			apply(pos*2,l,mid,lazy[pos]);
			apply(pos*2+1,mid+1,r,lazy[pos]);
		}
		lazy[pos]=0;
	}
	void pull(int pos,int l,int r){
		mn[pos]=min(mn[pos*2],mn[pos*2+1]);
		val[pos]=min(val[pos*2],val[pos*2+1]);
		cnt[pos]=cnt[pos*2]+cnt[pos*2+1];
	}
	void updateadd(int ql,int qr,int val,int l,int r,int pos=1){
		if(l>qr||r<ql)return;
		if(ql<=l&&r<=qr)return void(apply(pos,l,r,val));
		int mid=l+(r-l)/2;
		push(pos,l,r);
		updateadd(ql,qr,val,l,mid,pos*2);
		updateadd(ql,qr,val,mid+1,r,pos*2+1);
		pull(pos,l,r);
	}
	void toggle(int qpos,int l,int r,int pos=1){
		if(l>qpos||r<qpos)return;
		if(l==r){
			if(cnt[pos])mn[pos]=inf;
			else mn[pos]=val[pos];
			cnt[pos]=!cnt[pos];
			return;
		}
		int mid=l+(r-l)/2;
		push(pos,l,r);
		toggle(qpos,l,mid,pos*2);
		toggle(qpos,mid+1,r,pos*2+1);
		pull(pos,l,r);
	}
	int qry(int qpos,int l,int r,int pos=1){
		if(l>qpos||r<qpos)return inf;
		if(l==r)return val[pos];
		int mid=l+(r-l)/2;
		push(pos,l,r);
		return min(qry(qpos,l,mid,pos*2),qry(qpos,mid+1,r,pos*2+1));
	}
}t;
vector<pair<pii,pii>>event;
//time , upd val , id , type
int tin[mxn+10],tout[mxn+10],T=0,N;
void dfs(int cur,int p){
	tin[cur]=++T;
	for(auto j:node_qry[cur])event.pb({{j,0},{cur,1}});
	for(auto j:node_update[cur])event.pb({{j,0},{cur,2}});
	for(auto i:adj[cur])if(i.f!=p&&!del[i.f]){
		dfs(i.f,cur);
		t.updateadd(tin[i.f],tout[i.f],W[i.s],1,N);
		CW[i.s]=W[i.s];
		for(auto j:edge_update[i.s])event.pb({{j.f,j.s},{i.s,3}});
	}
	tout[cur]=T;
}
void solve(int cur){
	T=0;
	getsz(cur,-1);
	N=sz[cur];
	int node=getcen(cur,-1,sz[cur]/2);
	t.init(N);
	dfs(node,-1);
	sort(all(event));
	for(auto i:event){
		if(i.s.s==1){
			//qry
			ans[i.f.f]=min(ans[i.f.f],t.qry(tin[i.s.f],1,N)+t.mn[1]);
		}
		else if(i.s.s==2){
			//toggle
			t.toggle(tin[i.s.f],1,N);
		}
		else{
			if(tin[E[i.s.f].f]<tin[E[i.s.f].s])swap(E[i.s.f].f,E[i.s.f].s);
			t.updateadd(tin[E[i.s.f].f],tout[E[i.s.f].f],-CW[i.s.f]+i.f.s,1,N);
			CW[i.s.f]=i.f.s;
		}
	}
	event.clear();
	del[node]=1;
	for(auto i:adj[node])if(!del[i.f])solve(i.f);
}
int32_t main(){
	fastio
	cin>>n>>q;
	map<pii,int>mp;
	for(int i=0;i<n-1;i++){
		int a,b,c;cin>>a>>b>>c;
		E[i]={a,b};
		adj[a].pb({b,i});
		adj[b].pb({a,i});
		mp[{min(a,b),max(a,b)}]=i;
		W[i]=c;
	}
	for(int i=0;i<q;i++){
		ans[i]=inf;
		int t;cin>>t;
		if(t==1){
			int a;cin>>a;
			yes[i]=1;
			node_qry[a].pb(i);
		}
		else if(t==2){
			int a;cin>>a;
			node_update[a].pb(i);
		}
		else{
			int a,b,c;cin>>a>>b>>c;
			edge_update[mp[{min(a,b),max(a,b)}]].pb({i,c});
		}
	}
	solve(1);
	for(int i=0;i<q;i++)if(yes[i])cout<<((ans[i]==inf)?-1:ans[i])<<'\n';
}
/*

*/

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:33:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   33 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Main.cpp:42:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   42 | void setIO(string name){
      |                       ^
Main.cpp:53:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 | void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i.f!=p&&!del[i.f])getsz(i.f,cur),sz[cur]+=sz[i.f];}
      |                         ^
Main.cpp:54:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 | int getcen(int cur,int p,int need){
      |                                  ^
Main.cpp:62:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   62 |         void init(int n){for(int i=0;i<=4*n;i++)mn[i]=inf,val[i]=cnt[i]=lazy[i]=0;}
      |                        ^
Main.cpp:63:45: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   63 |         void apply(int pos,int l,int r,int x){
      |                                             ^
Main.cpp:68:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   68 |         void push(int pos,int l,int r){
      |                                      ^
Main.cpp:76:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   76 |         void pull(int pos,int l,int r){
      |                                      ^
Main.cpp:81:67: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   81 |         void updateadd(int ql,int qr,int val,int l,int r,int pos=1){
      |                                                                   ^
Main.cpp:90:51: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   90 |         void toggle(int qpos,int l,int r,int pos=1){
      |                                                   ^
Main.cpp:104:47: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  104 |         int qry(int qpos,int l,int r,int pos=1){
      |                                               ^
Main.cpp:115:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  115 | void dfs(int cur,int p){
      |                       ^
Main.cpp:127:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  127 | void solve(int cur){
      |                   ^
Main.cpp:154:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  154 | int32_t main(){
      |              ^
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32