Submission #806910

#	Time	Username	Problem	Language	Result	Execution time	Memory
806910		thimote75	Synchronization (JOI13_synchronization)	C++14	40 / 100	8050 ms	37196 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

template<typename T>
string to_string(T x) {
    string S = "[";
    bool first = true;
    for (const auto v : x) {
        if (!first) S += ", ";
        S += to_string(v); 
        first = false;
    }
    S += "]";
    return S;
}

string to_string(string x) {
    return x;
}

template<typename A, typename B>
string to_string (pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out () { cout << endl; }
template<typename Head, typename... Tail>
void dbg_out (Head H, Tail... T) {
    cout << to_string(H) << " ";
    dbg_out(T...);
}

#ifdef DEBUG
#  define dbg(...) cout << "(" << #__VA_ARGS__ << "): ";  dbg_out(__VA_ARGS__);
#else
#  define dbg(...)
#endif

int N, M, Q;

struct Road {
    int a, b;
    
    set<int> time_start;
    set<int> time_end;
    bool status = false;

    int next (int node) {
        return a == node ? b : a;
    }

    int get_time (int time) {
        auto it_en = time_end.upper_bound(time);
        int tim_en = -5;
        if (it_en != time_end.begin()) {
            it_en --;
            tim_en = *it_en;
        }

        auto it_st = time_start.upper_bound(time);
        if (it_st != time_start.begin()) {
            it_st --;
            int time_st = (*it_st);

            if (tim_en < time_st) return time;
            return tim_en;
        } else return -1;
    }
};

vector<Road> road_array;

using idata = vector<int>;
using igrid = vector<idata>;

using graph = igrid;

graph roads;

int compute (int node, int parent, int timeMax) {
    int res = 1;

    for (int roadId : roads[node]) {
        Road &road = road_array[roadId];
        int next   = road.next(node);
        if (next == parent) continue ;

        int nTime = road.get_time(timeMax);
        if (nTime == -1) continue ;

        res += compute(next, node, nTime);
    }

    return res;
}

int main () {
    cin >> N >> M >> Q;

    roads.resize(N);

    for (int i = 1; i < N; i ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        Road road;
        road.a = a; road.b = b;
        road_array.push_back(road);

        roads[a].push_back(i - 1);
        roads[b].push_back(i - 1);
    }

    for (int i = 0; i < M; i ++) {
        int x; cin >> x; x --;

        road_array[x].status = !road_array[x].status;
        if (!road_array[x].status)
            road_array[x].time_end.insert(i);
        else road_array[x].time_start.insert(i);
    }

    for (int i = 0; i + 1 < N; i ++)
        if (road_array[i].status)
            road_array[i].time_end.insert(M);
    
    for (int q = 0; q < Q; q ++) {
        int x; cin >> x; x --;

        cout << compute(x, -1, M) << endl;
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40