五月天青色头像情侣网名,国产亚洲av片在线观看18女人,黑人巨茎大战俄罗斯美女,扒下她的小内裤打屁股

歡迎光臨散文網(wǎng) 會員登陸 & 注冊

CF Lane Switching 參考答案

2022-05-30 14:17 作者:信奧賽USACO鄭老師  | 我要投稿

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;


?bool can_pass(PII x,PII y,double limit){

? ? int maxf=max(x.first,y.first);

? ? int mins=min(x.second,y.second);

? ? if(mins-maxf-limit>=0){

? ? ? ? return true;

? ? }else{

? ? ? ? return false;

? ? }? ??

}? ??


bool reachLastLane(int start, vector<vector<int>>& net, int n, map<int, pair<int,int> >& v2p){

? ? stack<int> s;

? ? s.push(start);

? ? vector<bool> vis(n);

? ? while(!s.empty()){

? ? ? ? int a=s.top();

? ? ? ? s.pop();

? ? ? ? for(int v:net[a]){

? ? ? ? ? ? if(!vis[v]){

? ? ? ? ? ? ? ? if(v2p[v].first==n-1){

? ? ? ? ? ? ? ? ? ? return true;

? ? ? ? ? ? ? ? }else{

? ? ? ? ? ? ? ? ? ? vis[v]=true;

? ? ? ? ? ? ? ? ? ? s.push(v);

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? return false;

}? ??


int main()

{

? ? int n,m,r,acms,acml;

? ? cin>>n>>m>>r;

? ? int lane,len,start ;

? ? cin>>lane>>acml>>acms;

? ? vector< vector< pair<int,int> > > cars(n);

? ? vector< vector< pair<int,int> > > road(n);

? ? vector< vector< int > > p2v(n);

? ? map<int, pair<int,int> > v2p;

? ??

? ? for(int i=1;i<m;i++){

? ? ? ? cin>>lane>>len>>start;

? ? ? ? cars[lane].push_back(make_pair(start,start+len));

? ? }

? ? int vexnum=0;

? ? for(int i=0;i<n;i++){

? ? ? ? sort(cars[i].begin(),cars[i].end());

? ? ? ? int num=cars[i].size();


? ? ? ? if(num>0){

? ? ? ? ? ? road[i].push_back(make_pair(0,cars[i][0].first));

? ? ? ? }else{

? ? ? ? ? ? road[i].push_back(make_pair(0,r));

? ? ? ? }

? ? ? ? p2v[i].push_back(vexnum);

? ? ? ? v2p[vexnum]=make_pair(i,p2v[i].size()-1);

? ? ? ? vexnum++;

? ? ? ? for(int j=1;j<num;j++){

? ? ? ? ? ? road[i].push_back(make_pair(cars[i][j-1].second,cars[i][j].first));

? ? ? ? ? ? p2v[i].push_back(vexnum);

? ? ? ? ? ? v2p[vexnum]=make_pair(i,p2v[i].size()-1);

? ? ? ? ? ? vexnum++;

? ? ? ? }

? ? ? ? if(num>0){

? ? ? ? ? ? road[i].push_back(make_pair(cars[i][num-1].second,r));

? ? ? ? ? ? p2v[i].push_back(vexnum);

? ? ? ? ? ? v2p[vexnum]=make_pair(i,p2v[i].size()-1);

? ? ? ? ? ? vexnum++;

? ? ? ? }? ??

? ? }

? ? //find out start vex

? ? int startv;

? ? auto ip=upper_bound(road[0].begin(),road[0].end(),make_pair(acms,acms+r+1));

? ? ip--;

? ? int index=ip-road[0].begin();

? ? startv=p2v[0][index];

? ? ? ??

? ? double lf=-(double)acml/2, rt=((double)r+1)/2;

? ? while(rt-lf>1e-6){

? ? ? ? vector<vector<int>> net(vexnum);

? ? ? ? double md=(lf+rt)/2;

? ? ? ? double limit=2*md+acml;

? ? ? ? //construct net

? ? ? ? for(int i=0;i<n-1;i++){

? ? ? ? ? ? int k=0,l=0;

? ? ? ? ? ? while(k<road[i].size() && l<road[i+1].size()){

? ? ? ? ? ? ? ? if(can_pass(road[i][k],road[i+1][l],limit)){

? ? ? ? ? ? ? ? ? ? net[p2v[i][k]].push_back(p2v[i+1][l]);

? ? ? ? ? ? ? ? ? ? net[p2v[i+1][l]].push_back(p2v[i][k]);

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if(road[i][k].second>road[i+1][l].second){

? ? ? ? ? ? ? ? ? ? l++;

? ? ? ? ? ? ? ? }else{

? ? ? ? ? ? ? ? ? ? k++;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }? ??

? ? ? ? if(reachLastLane(startv, net, n, v2p)){

? ? ? ? ? ? lf=md;

? ? ? ? }else{

? ? ? ? ? ? rt=md;

? ? ? ? }

? ? }

? ? if(lf>=0){

? ? ? ? printf("%.5f\n",lf);

? ? }else{

? ? ? ? cout<<"Impossible"<<endl;

? ? }? ??

? ? return 0;

}


CF Lane Switching 參考答案的評論 (共 條)

分享到微博請遵守國家法律
南川市| 松桃| 涟源市| 南投市| 浮山县| 乃东县| 达州市| 涪陵区| 汉川市| 银川市| 云浮市| 凤翔县| 岐山县| 阳谷县| 泸州市| 安顺市| 通海县| 自贡市| 同仁县| 茌平县| 郓城县| 德江县| 冷水江市| 湄潭县| 松江区| 正镶白旗| 合作市| 武胜县| 武城县| 濮阳县| 龙泉市| 卫辉市| 遵义市| 莒南县| 襄汾县| 北票市| 兰州市| 澄迈县| 自治县| 环江| 咸阳市|