Submission #396870

#	Time	Username	Problem	Language	Result	Execution time	Memory
396870		ly20	Rail (IOI14_rail)	C++17	0 / 100	3097 ms	167632 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5123;
int marc[MAXN];
void findLocation(int n, int first, int location[], int stype[])
{
    location[0] = first;
    stype[0] = 1;
    marc[0] = 1;
    set <pair <int, pair <int, int> > > s;
    for(int i = 0; i < n; i++) {
        if(marc[i] == 1) continue;
        s.insert(make_pair(getDistance(0, i), make_pair(0, i)));
    }
    while(!s.empty()) {
        int a = (*(s.begin())).second.first, b = (*(s.begin())).second.second;
        int d = (*(s.begin())).first;
        s.erase(s.begin());
        if(marc[b] == 1) {
            continue;
        }
        if(stype[a] == 1) {
            stype[b] = 2;
            location[b] = location[a] + d - 1;
        }
        else {
            stype[b] = 1;
            location[b] = location[a] - d + 1;
        }
        marc[b] = 1;
        for(int i = 0; i < n; i++) {
            if(marc[i] == 1) continue;
            s.insert(make_pair(getDistance(b, i), make_pair(b, i)));
        }
    }
    return;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44