oj.uz

Submission #545801

# Submission time Handle Problem Language Result Execution time Memory
545801 2022-04-05T13:15:06 Z jamezzz Valley (BOI19_valley) C++17
59 / 100
 3000 ms 231280 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ll> il;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 100005

struct node{
	int n;
	vector<ll> lz;
	vector<il> v;
	void init(int _n){
		n=_n;
		v.resize(4*n,{0,0});
		lz.resize(4*n,0);
	}
	void ppo(int i,int s,int e){
		v[i].se+=lz[i];
		if(s!=e){
			lz[2*i+1]+=lz[i];
			lz[2*i+2]+=lz[i];
		}
		lz[i]=0;
	}
	void up(int i,int s,int e,int x,int y,ll nv){
		if(s==x&&e==y){
			lz[i]+=nv;return;
		}
		int m=(s+e)>>1;
		if(y<=m)up(2*i+1,s,m,x,y,nv);
		else if(x>m)up(2*i+2,m+1,e,x,y,nv);
		else up(2*i+1,s,m,x,m,nv),up(2*i+2,m+1,e,m+1,y,nv);
		ppo(2*i+1,s,m);ppo(2*i+2,m+1,e);
		v[i]=min(v[2*i+1],v[2*i+2]);
	}
	void up(int x,int y,ll nv){
		up(0,0,n-1,x,y,nv);
	}
	void set(int i,int s,int e,int x,int t){
		if(s==x&&e==x){
			v[i].fi=t;return;
		}
		int m=(s+e)>>1;
		if(x<=m)set(2*i+1,s,m,x,t);
		else set(2*i+2,m+1,e,x,t);
		ppo(2*i+1,s,m);ppo(2*i+2,m+1,e);
		v[i]=min(v[2*i+1],v[2*i+2]);
	}
	void set(int x,int t){
		set(0,0,n-1,x,t);
	}
	il qry(int i,int s,int e,int x,int y){
		ppo(i,s,e);
		if(s==x&&e==y)return v[i];
		int m=(s+e)>>1;
		if(y<=m)return qry(2*i+1,s,m,x,y);
		if(x>m)return qry(2*i+2,m+1,e,x,y);
		return min(qry(2*i+1,s,m,x,m),qry(2*i+2,m+1,e,m+1,y));
	}
	il qry(int x,int y){
		if(x>y)return {2,LINF};
		return qry(0,0,n-1,x,y);
	}
}seg[maxn];

int n,q,s,e,w[maxn],sub[maxn];
vii AL[maxn];
bool shop[maxn],done[maxn];
vi nodeComp[maxn],edgeComp[maxn];
vii nodeRange[maxn],edgeRange[maxn];
ii block[maxn];
int cnt;

void calc(int u,int p){
	sub[u]=1;
	for(auto[v,i]:AL[u]){
		if(v==p||done[v])continue;
		calc(v,u);
		sub[u]+=sub[v];
	}
}

void dfs(int u,int p,int c){
	ii rng={cnt,cnt};++cnt;
	for(auto[v,i]:AL[u]){
		if(v==p||done[v])continue;
		dfs(v,u,c);
		ii tmp=nodeRange[v].back();
		rng.se=max(rng.se,tmp.se);
		edgeComp[i].pb(c);
		edgeRange[i].pb(tmp);
	}
	nodeComp[u].pb(c);
	nodeRange[u].pb(rng);
}

void decomp(int u){
	calc(u,-1);
	int c=u;
	while(true){
		bool val=true;
		for(auto[v,i]:AL[c]){
			if(done[v])continue;
			if(sub[v]<sub[c]&&sub[v]>sub[u]/2){
				c=v;val=false;
			}
		}
		if(val)break;
	}
	
	cnt=0;
	dfs(c,-1,c);
	seg[c].init(cnt);
	
	done[c]=true;
	for(auto[v,i]:AL[c]){
		if(!done[v])decomp(v);
	}
}

int main(){
	sf("%d%d%d%d",&n,&s,&q,&e);
	for(int i=1;i<n;++i){
		int a,b;
		sf("%d%d%d",&a,&b,&w[i]);
		AL[a].pb({b,i});
		AL[b].pb({a,i});
	}
	for(int i=0;i<s;++i){
		int c;sf("%d",&c);
		shop[c]=true;
	}
	
	decomp(1);
	
	for(int i=1;i<n;++i){
		for(int j=0;j<sz(edgeComp[i]);++j){
			int c=edgeComp[i][j];
			ii r=edgeRange[i][j];
			seg[c].up(r.fi,r.se,w[i]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<sz(nodeComp[i]);++j){
			int c=nodeComp[i][j];
			ii r=nodeRange[i][j];
			if(i==e)seg[c].set(r.fi,0);
			else if(shop[i])seg[c].set(r.fi,1);
			else seg[c].set(r.fi,2);
		}
	}
	
	for(int i=1;i<=n;++i)block[i]={seg[i].n,-1};
	
	for(int i=0;i<q;++i){
		int x,s;sf("%d%d",&x,&s);
		
		for(int i=0;i<sz(edgeComp[x]);++i){
			block[edgeComp[x][i]]=edgeRange[x][i];
		}
		
		ll ans=LINF;
		for(int i=0;i<sz(nodeComp[s]);++i){
			int c=nodeComp[s][i];
			ii r=nodeRange[s][i];
			if(block[c].fi<=r.fi&&r.fi<=block[c].se)continue;//path to this is blocked
			il d1=seg[c].qry(r.fi,r.fi);
			if(d1.fi==0)ans=-1;
			else if(d1.fi==1)ans=min(ans,0ll);
			il d2=min(seg[c].qry(0,block[c].fi-1),seg[c].qry(block[c].se+1,seg[c].n-1));
			if(d2.fi==0)ans=-1;
			else if(d2.fi==1)ans=min(ans,d1.se+d2.se);
		}
		
		for(int i=0;i<sz(edgeComp[x]);++i){
			int c=edgeComp[x][i];
			block[c]={seg[c].n,-1};
		}
		
		if(ans==LINF)pf("oo\n");
		else if(ans==-1)pf("escaped\n");
		else pf("%lld\n",ans);
	}
}

/*
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
*/

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:174:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |  sf("%d%d%d%d",&n,&s,&q,&e);
      |    ^
valley.cpp:177:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |   sf("%d%d%d",&a,&b,&w[i]);
      |     ^
valley.cpp:182:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |   int c;sf("%d",&c);
      |           ^
valley.cpp:208:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |   int x,s;sf("%d%d",&x,&s);
      |             ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17772 KB Output is correct
2 Correct 19 ms 17724 KB Output is correct
3 Correct 19 ms 17688 KB Output is correct
4 Correct 20 ms 17684 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17772 KB Output is correct
2 Correct 19 ms 17724 KB Output is correct
3 Correct 19 ms 17688 KB Output is correct
4 Correct 20 ms 17684 KB Output is correct
5 Correct 17 ms 18168 KB Output is correct
6 Correct 18 ms 18436 KB Output is correct
7 Correct 21 ms 18616 KB Output is correct
8 Correct 17 ms 18108 KB Output is correct
9 Correct 18 ms 18452 KB Output is correct
10 Correct 19 ms 18712 KB Output is correct
11 Correct 13 ms 18204 KB Output is correct
12 Correct 15 ms 18320 KB Output is correct
13 Correct 16 ms 18624 KB Output is correct
14 Correct 17 ms 18584 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 100856 KB Output is correct
2 Correct 1970 ms 149868 KB Output is correct
3 Correct 2516 ms 182336 KB Output is correct
4 Correct 2778 ms 211308 KB Output is correct
5 Correct 2719 ms 211860 KB Output is correct
6 Correct 2883 ms 231280 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17772 KB Output is correct
2 Correct 19 ms 17724 KB Output is correct
3 Correct 19 ms 17688 KB Output is correct
4 Correct 20 ms 17684 KB Output is correct
5 Correct 17 ms 18168 KB Output is correct
6 Correct 18 ms 18436 KB Output is correct
7 Correct 21 ms 18616 KB Output is correct
8 Correct 17 ms 18108 KB Output is correct
9 Correct 18 ms 18452 KB Output is correct
10 Correct 19 ms 18712 KB Output is correct
11 Correct 13 ms 18204 KB Output is correct
12 Correct 15 ms 18320 KB Output is correct
13 Correct 16 ms 18624 KB Output is correct
14 Correct 17 ms 18584 KB Output is correct
15 Correct 1137 ms 100856 KB Output is correct
16 Correct 1970 ms 149868 KB Output is correct
17 Correct 2516 ms 182336 KB Output is correct
18 Correct 2778 ms 211308 KB Output is correct
19 Correct 2719 ms 211860 KB Output is correct
20 Correct 2883 ms 231280 KB Output is correct
21 Correct 991 ms 100112 KB Output is correct
22 Correct 1660 ms 152676 KB Output is correct
23 Correct 2142 ms 182928 KB Output is correct
24 Execution timed out 3045 ms 211072 KB Time limit exceeded
25 Halted 0 ms 0 KB -