oj.uz

Submission #806910

# Submission time Handle Problem Language Result Execution time Memory
806910 2023-08-04T11:00:26 Z thimote75 Synchronization (JOI13_synchronization) C++14
40 / 100
 8000 ms 37196 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 11 ms 3276 KB Output is correct
8 Correct 11 ms 3308 KB Output is correct
9 Correct 13 ms 3316 KB Output is correct
10 Correct 147 ms 30760 KB Output is correct
11 Correct 167 ms 30944 KB Output is correct
12 Correct 137 ms 30656 KB Output is correct
13 Correct 130 ms 30732 KB Output is correct
14 Correct 127 ms 27864 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 35704 KB Output is correct
2 Correct 119 ms 33140 KB Output is correct
3 Correct 96 ms 34572 KB Output is correct
4 Correct 95 ms 33436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 26 ms 3304 KB Output is correct
8 Correct 294 ms 31500 KB Output is correct
9 Correct 289 ms 31492 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 28564 KB Output is correct
2 Execution timed out 8050 ms 37196 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 132 ms 3376 KB Output is correct
7 Correct 4400 ms 31784 KB Output is correct
8 Correct 285 ms 31456 KB Output is correct
9 Execution timed out 8016 ms 31012 KB Time limit exceeded
10 Halted 0 ms 0 KB -