Submission #2980542


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005,maxm=200005;
const long long INF=200000000000000ll;
struct A{
	int x;
	long long d;
	A(int x,long long d):x(x),d(d){}
	bool operator<(const A &a)const{return d>a.d;}
};
struct node{
	long long key,lazy;
	bool bad;
	int d;
	node *lc,*rc;
	node(){}
	node(long long key):key(key),lazy(0),bad(false),d(0){}
	void pushdown(){
		if(!lazy)return;
		key+=lazy;
		lc->lazy+=lazy;
		rc->lazy+=lazy;
		lazy=0;
	}
	void refresh(){d=rc->d+1;}
}null[maxm<<1],*ptr=null,*root[maxn];
void Dijkstra(int);
int LCA(int,int);
node *newnode(long long);
node *merge(node*,node*);
long long top(node*&);
int findroot(int);
void mergeset(int,int);
vector<int>G[maxn],W[maxn];
vector<node*>v[maxn];
long long d[maxn],ds[maxn],c[maxn];
bool vis[maxn];
int p[maxn],depth[maxn],f[maxn][20],q[maxn];
int n,m,s,t;
int main(){
	null->key=INF;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=0;i<=n;i++)root[i]=null;
	while(m--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back(y);
		W[x].push_back(z);
		G[y].push_back(x);
		W[y].push_back(z);
	}
	Dijkstra(s);
	memcpy(ds,d,sizeof(d));
	Dijkstra(t);
	for(int i=1;i<=n;i++)
		f[i][0]=p[i];
	for(int j=1;(1<<j)<n;j++)
		for(int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	memset(vis,0,sizeof(vis));
	for(int x=1;x<=n;x++)
		if(d[x]<INF){
			for(int i=0;i<(int)G[x].size();i++){
				if(!vis[x]&&G[x][i]==p[x]&&W[x][i]==d[x]-d[p[x]]){
					vis[x]=true;
					continue;
				}
				root[x]=merge(root[x],newnode(d[G[x][i]]+W[x][i]));
				int u=LCA(x,G[x][i]);
				v[u].push_back(ptr);
			}
		}
	for(int i=1;i<=n;i++)q[i]=i;
	sort(q+1,q+n+1,[](int x,int y){return d[x]>d[y];});
	for(int k=1;k<n;k++){
		int x=q[k];
		for(auto t:v[x])t->bad=true;
		c[x]=ds[x]+top(root[x]);
		root[x]->lazy+=d[x]-d[p[x]];
		root[p[x]]=merge(root[p[x]],root[x]);
	}
	for(int k=n-1;k;k--){
		int x=q[k];
		c[x]=max(c[x],c[p[x]]-(d[x]-d[p[x]])*2);
	}
	sort(q+1,q+n+1,[](int x,int y){return c[x]<c[y];});
	memset(p,0,sizeof(p));
	bool ok=false;
	for(int k=1;k<=n;k++){
		int x=q[k];
		if(c[x]>=INF)break;
		p[x]=x;
		for(int i=0;i<(int)G[x].size();i++)
			if(p[G[x][i]])mergeset(x,G[x][i]);
		if(p[x]&&p[t]&&findroot(s)==findroot(t)){
			printf("%lld\n",c[x]);
			ok=true;
			break;
		}
	}
	if(!ok)printf("-1\n");
	return 0;
}
void Dijkstra(int s){
	for(int i=1;i<=n;i++)d[i]=INF;
	memset(vis,0,sizeof(vis));
	memset(p,0,sizeof(p));
	memset(depth,0,sizeof(depth));
	d[s]=0;
	priority_queue<A>heap;
	heap.push(A(s,0));
	while(!heap.empty()){
		int x=heap.top().x;
		heap.pop();
		if(vis[x])continue;
		vis[x]=true;
		depth[x]=depth[p[x]]+1;
		for(int i=0;i<(int)G[x].size();i++)
			if(!vis[G[x][i]]&&d[G[x][i]]>d[x]+W[x][i]){
				d[G[x][i]]=d[x]+W[x][i];
				p[G[x][i]]=x;
				heap.push(A(G[x][i],d[G[x][i]]));
			}
	}
}
int LCA(int x,int y){
	if(depth[x]!=depth[y]){
		if(depth[x]<depth[y])swap(x,y);
		int t=depth[x]-depth[y];
		for(int i=19;~i;i--)
			if((t>>i)&1)x=f[x][i];
	}
	if(x==y)return x;
	for(int i=19;~i;i--)
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	return f[x][0];
}
node *newnode(long long key){
	*++ptr=node(key);
	ptr->lc=ptr->rc=null;
	return ptr;
}
node *merge(node *x,node *y){
	if(x==null)return y;
	if(y==null)return x;
	x->pushdown();
	y->pushdown();
	if(x->key>y->key)swap(x,y);
	x->rc=merge(x->rc,y);
	if(x->rc->d>x->lc->d)swap(x->lc,x->rc);
	x->refresh();
	return x;
}
long long top(node *&x){
	while(x!=null&&x->bad){
		x->pushdown();
		x=merge(x->lc,x->rc);
	}
	if(x!=null)x->pushdown();
	return x->key;
}
int findroot(int x){return x==p[x]?x:p[x]=findroot(p[x]);}
void mergeset(int x,int y){p[findroot(x)]=findroot(y);}

Submission Info

Submission Time
Task D - Revenge of the Broken Door
User AntiLeaf
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3791 Byte
Status WA
Exec Time 318 ms
Memory 44588 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&n,&m,&s,&t);
                               ^
./Main.cpp:46:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x,&y,&z);
                           ^

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 49
WA × 17
Set Name Test Cases
All 00_sample_00, 00_sample_01, 00_sample_02, 10_small_0, 10_small_1, 10_small_2, 10_small_3, 10_small_4, 10_small_5, 10_small_6, 10_small_7, 10_small_8, 10_small_9, 20_med_0, 20_med_1, 20_med_2, 20_med_3, 20_med_4, 20_med_5, 20_med_6, 21_med_0, 21_med_1, 21_med_2, 30_large_0, 30_large_1, 30_large_2, 30_large_3, 30_large_4, 30_large_5, 30_large_6, 31_large_0, 31_large_1, 31_large_2, 40_circle_0, 40_circle_1, 40_circle_2, 40_circle_3, 40_circle_4, 41_impossible_0, 41_impossible_1, 41_impossible_2, 42_special_0, 42_special_1, 42_special_10, 42_special_11, 42_special_12, 42_special_13, 42_special_14, 42_special_2, 42_special_3, 42_special_4, 42_special_5, 42_special_6, 42_special_7, 42_special_8, 42_special_9, 43_special_0, 43_special_1, 43_special_2, 43_special_3, 43_special_4, 43_special_5, 43_special_6, 43_special_7, 43_special_8, 43_special_9
Case Name Status Exec Time Memory
00_sample_00 AC 4 ms 12544 KB
00_sample_01 AC 4 ms 12544 KB
00_sample_02 AC 4 ms 12544 KB
10_small_0 AC 4 ms 12544 KB
10_small_1 AC 4 ms 12544 KB
10_small_2 AC 4 ms 12544 KB
10_small_3 AC 4 ms 12544 KB
10_small_4 AC 4 ms 12544 KB
10_small_5 AC 4 ms 12544 KB
10_small_6 AC 4 ms 12544 KB
10_small_7 AC 4 ms 12544 KB
10_small_8 AC 4 ms 12544 KB
10_small_9 AC 4 ms 12544 KB
20_med_0 AC 111 ms 31728 KB
20_med_1 AC 6 ms 12800 KB
20_med_2 AC 42 ms 19636 KB
20_med_3 WA 84 ms 24920 KB
20_med_4 WA 116 ms 31688 KB
20_med_5 AC 121 ms 28880 KB
20_med_6 WA 62 ms 23572 KB
21_med_0 AC 52 ms 21680 KB
21_med_1 AC 123 ms 28676 KB
21_med_2 AC 130 ms 33068 KB
30_large_0 AC 125 ms 29168 KB
30_large_1 WA 31 ms 16920 KB
30_large_2 WA 64 ms 22084 KB
30_large_3 WA 127 ms 32340 KB
30_large_4 WA 64 ms 20688 KB
30_large_5 AC 115 ms 28216 KB
30_large_6 AC 138 ms 32564 KB
31_large_0 AC 88 ms 24556 KB
31_large_1 AC 151 ms 32856 KB
31_large_2 AC 128 ms 32388 KB
40_circle_0 AC 90 ms 34176 KB
40_circle_1 AC 91 ms 34176 KB
40_circle_2 AC 91 ms 34176 KB
40_circle_3 AC 91 ms 34176 KB
40_circle_4 AC 91 ms 34176 KB
41_impossible_0 AC 318 ms 44332 KB
41_impossible_1 AC 293 ms 44588 KB
41_impossible_2 AC 288 ms 44588 KB
42_special_0 AC 90 ms 34176 KB
42_special_1 AC 95 ms 34176 KB
42_special_10 AC 122 ms 34176 KB
42_special_11 AC 129 ms 34192 KB
42_special_12 AC 137 ms 34240 KB
42_special_13 AC 146 ms 34172 KB
42_special_14 AC 163 ms 36276 KB
42_special_2 AC 100 ms 34176 KB
42_special_3 AC 106 ms 34176 KB
42_special_4 AC 108 ms 34176 KB
42_special_5 AC 111 ms 34176 KB
42_special_6 AC 112 ms 34176 KB
42_special_7 AC 115 ms 34176 KB
42_special_8 AC 115 ms 34176 KB
42_special_9 AC 117 ms 34176 KB
43_special_0 WA 120 ms 34048 KB
43_special_1 WA 121 ms 34048 KB
43_special_2 WA 119 ms 34048 KB
43_special_3 WA 120 ms 33920 KB
43_special_4 WA 120 ms 33920 KB
43_special_5 WA 120 ms 33920 KB
43_special_6 WA 120 ms 33920 KB
43_special_7 WA 121 ms 34048 KB
43_special_8 WA 122 ms 33920 KB
43_special_9 WA 123 ms 34048 KB