oj.uz

답안 #252344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252344 2020-07-25T10:43:55 Z IgorI 동기화 (JOI13_synchronization) C++17
60 / 100
 8000 ms 19444 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 n, m, q;

int Get(int pos, vector<int> &tree, int L = 0, int R = n, int V = 0)
{
    if (tree[V] != -1)
    {
        return tree[V];
    }
    int M = (L + R) / 2;
    if (pos < M) return Get(pos, tree, L, M, 2 * V + 1);
    else return Get(pos, tree, M, R, 2 * V + 2);
}

void Set(int l, int r, int x, vector<int> &tree, int L = 0, int R = n, int V = 0)
{
    if (r <= L || R <= l)
    {
        return;
    }
    if (l <= L && R <= r)
    {
        tree[V] = x;
        return;
    }
    int M = (L + R) / 2;
    if (tree[V] != -1) tree[2 * V + 1] = tree[V];
    if (tree[V] != -1) tree[2 * V + 2] = tree[V];
    tree[V] = -1;
    Set(l, r, x, tree, L, M, 2 * V + 1);
    Set(l, r, x, tree, M, R, 2 * V + 2);
}

void solve_line()
{
    vector<int> le(4 * n, -1), ri(4 * n, -1);
    for (int i = 0; i < n; i++)
    {
        Set(i, i + 1, i, le);
        Set(i, i + 1, i, ri);
    }
    vector<int> act(n - 1);
    for (int i = 0; i < m; i++)
    {
        int z;
        cin >> z;
        z--;
        if (act[z])
        {
            act[z] = 0;
            continue;
        }
        act[z] = 1;
        int r = z;
        while (r < n - 1 && act[r]) r++;
        int l = z;
        while (l >= 0 && act[l]) l--;
        l++;
        Set(l, r + 1, Get(z + 1, ri), ri);
        Set(l, r + 1, Get(z, le), le);
    }
    vector<int> ans(n);
    for (int i = 0; i < n; i++)
    {
        ans[i] = Get(i, ri) - Get(i, le) + 1;
    }
    for (int i = 0; i < q; i++)
    {
        int v;
        cin >> v;
        v--;
        cout << ans[v] << "\n";
    }
}

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);
    cin >> n >> m >> q;
    vector<int> x(n - 1), y(n - 1);
    vector<vector<int> > graph(n);
    int line = 1;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> x[i] >> y[i];
        x[i]--, y[i]--;
        if (x[i] != i || y[i] != i + 1) line = 0;
        graph[x[i]].push_back(i);
        graph[y[i]].push_back(i);
    }
    if (line)
    {
        solve_line();
        return 0;
    }
    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

# 결과 실행 시간 메모리 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 0 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 8 ms 1536 KB Output is correct
8 Correct 7 ms 1536 KB Output is correct
9 Correct 11 ms 1536 KB Output is correct
10 Correct 100 ms 12280 KB Output is correct
11 Correct 102 ms 12280 KB Output is correct
12 Correct 198 ms 10616 KB Output is correct
13 Correct 75 ms 12532 KB Output is correct
14 Correct 77 ms 12536 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 19444 KB Output is correct
2 Correct 63 ms 16244 KB Output is correct
3 Correct 2627 ms 10616 KB Output is correct
4 Correct 2716 ms 10616 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 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 0 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 17 ms 1408 KB Output is correct
8 Correct 210 ms 10692 KB Output is correct
9 Correct 210 ms 10744 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 10744 KB Output is correct
2 Correct 2714 ms 11392 KB Output is correct
3 Correct 2651 ms 13560 KB Output is correct
4 Correct 2622 ms 13648 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 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 384 KB Output is correct
6 Correct 92 ms 1584 KB Output is correct
7 Correct 5200 ms 12720 KB Output is correct
8 Correct 207 ms 10744 KB Output is correct
9 Execution timed out 8071 ms 12588 KB Time limit exceeded
10 Halted 0 ms 0 KB -