oj.uz

Submission #252341

# Submission time Handle Problem Language Result Execution time Memory
252341 2020-07-25T10:14:30 Z IgorI Synchronization (JOI13_synchronization) C++17
40 / 100
 8000 ms 26792 KB 
const int LG = 21;
const int N = 200005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int dfs(int v, int p, int t, vvi &graph, vi &x, vi &y, vector<vector<pii> > &act)
{
    int res = 1;
    for (auto i : graph[v])
    {
        int u = x[i] + y[i] - v;
        if (u != p)
        {
            int L = -1, R = act[i].size();
            while (L + 1 < R)
            {
                int M = (L + R) / 2;
                if (act[i][M].first <= t)
                    L = M;
                else
                    R = M;
            }
            if (L == -1) continue;
            int T = min(act[i][L].second, t);
            res += dfs(u, v, T, graph, x, y, act);
        }
    }
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> x(n - 1), y(n - 1);
    vector<vector<int> > graph(n);
    for (int i = 0; i < n - 1; i++)
    {
        cin >> x[i] >> y[i];
        x[i]--, y[i]--;
        graph[x[i]].push_back(i);
        graph[y[i]].push_back(i);
    }
    vector<int> fr(n - 1, -1);
    vector<vector<pii> > act(n - 1);
    for (int i = 0; i < m; i++)
    {
        int z;
        cin >> z;
        z--;
        if (fr[z] == -1)
        {
            fr[z] = i;
        }
        else
        {
            act[z].push_back({fr[z], i});
            fr[z] = -1;
        }
    }
    for (int i = 0; i < n - 1; i++)
    {
        if (fr[i] != -1)
        {
            act[i].push_back({fr[i], m});
        }
    }
    for (int i = 0; i < q; i++)
    {
        int v;
        cin >> v;
        v--;
        cout << dfs(v, v, m, graph, x, y, act) << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 7 ms 1664 KB Output is correct
8 Correct 7 ms 1792 KB Output is correct
9 Correct 7 ms 1664 KB Output is correct
10 Correct 86 ms 14588 KB Output is correct
11 Correct 82 ms 14584 KB Output is correct
12 Correct 79 ms 14584 KB Output is correct
13 Correct 66 ms 14448 KB Output is correct
14 Correct 79 ms 14328 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 19316 KB Output is correct
2 Correct 63 ms 18308 KB Output is correct
3 Correct 66 ms 25720 KB Output is correct
4 Correct 61 ms 23928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 10 ms 1792 KB Output is correct
8 Correct 124 ms 15224 KB Output is correct
9 Correct 120 ms 15356 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 12320 KB Output is correct
2 Execution timed out 8058 ms 26792 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 92 ms 1792 KB Output is correct
7 Correct 3973 ms 15628 KB Output is correct
8 Correct 140 ms 15352 KB Output is correct
9 Execution timed out 8073 ms 14892 KB Time limit exceeded
10 Halted 0 ms 0 KB -