Brief description:

Problem C. Cruise Control
给定一条无限长的双车道的单行道，n 量车的信息 (Li, Si, Pi) 表示初始在哪个车道、速度、和当前位置，
问第一次发生碰撞事件的时间。(每辆车车长 5m，车辆在旁边没有车时，可以任意切换车道且不计时间。)
…

Analysis:

Problem C. Cruise Control
对每辆车可能的相遇区间选取关键时间建立事件，排序。。。
。。之后 用并查集 暴力维护染色信息即可
（。。其实就是有一些点已经染色的情况下做二分图判定。。并查集貌似会比较麻烦。。因为有拆解的情况产生呀。。。）
…

// <<= ' 0. I/O Accelerator interface .,

template<class T> inline void RD(T &x){
    //cin >> x;
    scanf("%d", &x);
    //char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
}

int ____Case;
template<class T> inline void OT(const T &x){
    printf("Case #%d: ", ++____Case);
    //printf("%d", x);
    printf("%.9f", x);
    puts("");
}

/* .................................................................................................................................. */

const int N = 100009;
DB P[N], tmp, res, cur;
int A, B;

int main(){

    //freopen("A-small-attempt0.in", "r", stdin);
    freopen("A-large.in", "r", stdin);
    //freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    Rush{
        RD(A, B); REP(i, A) scanf("%lf", &P[i]); res = OO;

        res = B + 2, tmp = 1;
        DWN_1(i, A, 0){            
            cur = (DB) (2 * i + B - A + 1 + B + 1) - tmp * (B + 1);            
            checkMin(res, cur);
            tmp *= P[A - i];
        }

        OT(res);
    }
}

// <<= ' 0. I/O Accelerator interface .,

template<class T> inline void RD(T &x){
    //cin >> x;
    scanf("%d", &x);
    //char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
}

bool failed;

int ____Case;
template<class T> inline void OT(const T &x){
    printf("Case #%d: ", ++____Case);
    if (failed) puts("Too Bad");
    else {
        printf("%d", x); puts("");
    }
}

/* .................................................................................................................................. */

const int N = 1009;
int a[N], b[N], c[N], star, tt;
int n;

int main(){

    //freopen("B-large-practice.in", "r", stdin);
    //freopen("A-large.in", "r", stdin);
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    Rush{

        REP_C(i, _RD(n)) RD(a[i], b[i]); b[n] = -INF;

        int j; RST(c); failed = false; star = tt = 0; while (star < 2*n && !failed){

            ++tt;

            REP(i, n) if (c[i] < 2 && star >= b[i]){
                star += 2 - c[i], c[i] = 2;
                goto A;
            }

            j = n; REP(i, n) if (c[i] < 1 && star >= a[i]){
                if (b[i] > b[j]) j = i;
            }

            if (j != n){
                star += 1, c[j] = 1;
                goto A;
            }

            failed = true;
            A:;
        }

        OT(tt);
    }
}

const int N = 59;

bool G[N][N]; int lane[N], pos[N], spd[N], tmp[N];
int n;


bool dfs(int u, int c) {
    if (lane[u] && lane[u] != c) return false;
    if (tmp[u]) return tmp[u] == c;

    tmp[u] = c; REP(v, n){
        if (G[u][v] && !dfs(v, c * -1)) return false;
    }
    return true;
}

vector<DB> L;

int main() {

    //freopen("C-small-practice.in", "r", stdin);
    freopen("C-large-practice.in", "r", stdin);
    //freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);


    Rush{

        CLR(L); L.PB(0);

        char dir; REP_C(i, _RD(n)){
            lane[i] = _RC(dir) == 'L' ? -1 : 1;
            RD(spd[i], pos[i]);
        }

        REP(i, n) REP(j, n) if (spd[j] > spd[i]){
            DB speed = spd[j] - spd[i]; if (pos[i] + 5 > pos[j]) {
                L.PB(DB(pos[i]+5-pos[j])/speed);
                if (pos[i] > pos[j]) {
                    L.PB(DB(pos[i]-pos[j])/speed);
                    if (pos[i] - 5 > pos[j]) L.PB(DB(pos[i]-5-pos[j])/speed);
                }
            }
        }

        res = 0; SRT(L); RST(G); int ii; REP_N(ii, SZ(L)){

                REP(i, n){
                    bool coll = false; REP(j, n) if (j != i) {
                    DB pi = pos[i] + spd[i] * L[ii], pj = pos[j] + spd[j] * L[ii];
                    if (sgn(abs(pi - pj), 5) < 0){
                        G[i][j] = G[j][i] = true;
                        coll = true;
                    }
                }

                if (!coll) {
                    for (int j = 0; j < N; j++) G[i][j] = G[j][i] = 0;
                    lane[i] = 0;
                }
            }

            REP(i, n) if (!lane[i]){
                RST(tmp); bool lv = dfs(i, -1);
                RST(tmp); bool rv = dfs(i, 1);

                if (!lv && !rv) goto Done;
                if (!lv && rv) lane[i] = 1;
                if (lv && !rv) lane[i] = -1;
            }
            else {
                RST(tmp); if (!dfs(i, lane[i])) goto Done;
            }

            res = L[ii];
        }

Done:
        printf("Case #%d: ", ++____Case);
        if (ii == SZ(L)) puts("Possible");
        else printf("%.9lf\n", res);
    }
}

Posted by xiaodao
Category: Google Code Jam