oj.uz

답안 #493833

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493833 2021-12-13T06:19:12 Z nathanlee726 Robot (JOI21_ho_t4) C++14
34 / 100
 3000 ms 682988 KB 
#include<bits/stdc++.h>
using namespace std; 
#define ll long long
#define int ll
#define pii pair<int,int>
#define X first
#define Y second
#define F(n) Fi(i,n) 
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define abs(x) ((x)>0?(x):-(x))
#define pb push_back

int n,m,ind,rr[2000010],d[2000010];
vector<pair<pii,pii> >g[2000010],rg[2000010];
map<pii,int> mmp;
bool used[2000010];

void calc(int x){
	map<int,int> mp;
	for(auto pt:g[x]){
		mp[pt.X.Y]+=pt.Y.X;
	}
	F(sz(g[x])){
		g[x][i].Y.Y=mp[g[x][i].X.Y]-g[x][i].Y.X;
	}
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	ind=n;
	F(m){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		--a,--b;
		g[a].pb({{b,c},{d,0}});
		g[b].pb({{a,c},{d,0}});
	}
	F(n)calc(i),rg[i]=g[i];
	vector<int> v;
	F(n){
		int tt=sz(g[i]);
		Fi(j,tt){
			mmp[{i,g[i][j].X.X}]=ind;
			rr[ind]=g[i][j].X.X;
			if(g[i][j].X.X==n-1)v.pb(ind);
			g[i].pb({{ind,-1},g[i][j].Y});
			g[ind]=rg[g[i][j].X.X];
			
			Fi(k,sz(g[ind])){
				if(g[ind][k].X.X!=i&&g[ind][k].X.Y==g[i][j].X.Y)g[ind][k].Y.Y-=g[i][j].Y.X;
				//if(g[ind][k].Y.Y<0)cout<<"c "<<g[ind][k].X.X<<" "<<g[ind][k].X.Y<<" "<<g[ind][k].Y.X<<" "<<g[ind][k].Y.Y<<endl;;
			}
			ind++;
		}
	}
	F(ind)d[i]=1e18;
	for(int i=n;i<ind;i++){
		for(auto pt:g[i]){
			int u=mmp[{rr[i],pt.X.X}];
			g[i].pb({{u,-1},{pt.Y}});
		}
	}
	priority_queue<pii,vector<pii>,greater<pii> >pq;
	pq.push({0,0});
	memset(used,0,sizeof(used));
	while(!pq.empty()){
		int p=pq.top().Y,ss=pq.top().X;pq.pop();
		if(used[p])continue;
		d[p]=ss;
		//cout<<"a "<<p<<" "<<ss<<endl;
		used[p]=1;
		for(auto pt:g[p]){
			if(pt.X.X>=n){
				pq.push({ss+pt.Y.X,pt.X.X});
			}
			else{
				pq.push({ss+pt.Y.Y,pt.X.X});
			}
		}
	}
	v.pb(n-1);
	int ans=1e18;
	//for(auto pt:g[6])cout<<pt.X.X<<" "<<pt.X.Y<<" "<<pt.Y.X<<" "<<pt.Y.Y<<endl;
	//cout<<d[4]<<endl;
	//F(n)cout<<d[i]<<" ";
	//cout<<endl;
	for(int i:v)ans=min(ans,d[i]);
	cout<<(ans>1e17?-1:ans)<<endl;
	return 0;
}

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 96152 KB Output is correct
2 Correct 47 ms 96108 KB Output is correct
3 Correct 55 ms 96224 KB Output is correct
4 Correct 49 ms 96196 KB Output is correct
5 Correct 50 ms 96320 KB Output is correct
6 Correct 49 ms 96356 KB Output is correct
7 Correct 66 ms 100996 KB Output is correct
8 Correct 53 ms 98344 KB Output is correct
9 Correct 1208 ms 238268 KB Output is correct
10 Correct 770 ms 189720 KB Output is correct
11 Correct 1909 ms 287612 KB Output is correct
12 Correct 481 ms 166272 KB Output is correct
13 Correct 1776 ms 285768 KB Output is correct
14 Correct 1654 ms 285672 KB Output is correct
15 Correct 53 ms 96984 KB Output is correct
16 Correct 61 ms 98660 KB Output is correct
17 Correct 69 ms 98336 KB Output is correct
18 Correct 52 ms 96616 KB Output is correct
19 Correct 164 ms 114964 KB Output is correct
20 Correct 60 ms 97472 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1513 ms 258552 KB Output is correct
2 Correct 463 ms 150576 KB Output is correct
3 Execution timed out 3107 ms 682988 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 96152 KB Output is correct
2 Correct 47 ms 96108 KB Output is correct
3 Correct 55 ms 96224 KB Output is correct
4 Correct 49 ms 96196 KB Output is correct
5 Correct 50 ms 96320 KB Output is correct
6 Correct 49 ms 96356 KB Output is correct
7 Correct 66 ms 100996 KB Output is correct
8 Correct 53 ms 98344 KB Output is correct
9 Correct 1208 ms 238268 KB Output is correct
10 Correct 770 ms 189720 KB Output is correct
11 Correct 1909 ms 287612 KB Output is correct
12 Correct 481 ms 166272 KB Output is correct
13 Correct 1776 ms 285768 KB Output is correct
14 Correct 1654 ms 285672 KB Output is correct
15 Correct 53 ms 96984 KB Output is correct
16 Correct 61 ms 98660 KB Output is correct
17 Correct 69 ms 98336 KB Output is correct
18 Correct 52 ms 96616 KB Output is correct
19 Correct 164 ms 114964 KB Output is correct
20 Correct 60 ms 97472 KB Output is correct
21 Correct 1513 ms 258552 KB Output is correct
22 Correct 463 ms 150576 KB Output is correct
23 Execution timed out 3107 ms 682988 KB Time limit exceeded
24 Halted 0 ms 0 KB -