oj.uz

Submission #995390

# Submission time Handle Problem Language Result Execution time Memory
995390 2024-06-09T02:36:23 Z cpptowin Synchronization (JOI13_synchronization) C++17
100 / 100
 250 ms 64584 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
int n,m,q;
vi ke[maxn];
struct BIT
{
    int t[maxn];
    void up(int x,int val)
    {
        for( ; x < maxn ; x += lb(x)) t[x] += val;
    }
    void up(int l,int r,int val)
    {
        up(l,val);
        up(r + 1,-val);
    }
    int get(int x)
    {
        int ans = 0;
        for( ; x ; x -= lb(x)) ans += t[x];
        return ans;
    }
}t;
int cnt,pos[maxn],tail[maxn],par[maxn][20];
void dfs(int u)
{
    pos[u] = ++cnt;
    for(int v : ke[u]) if(v != par[u][0])
    {
        par[v][0] = u;
        dfs(v);
    }
    tail[u] = cnt;
}
int find(int u)
{
    fod(i,19,0) if(t.get(pos[u]) == t.get(pos[par[u][i]])) u = par[u][i];
    return u;
}
int save[maxn];
bool on[maxn];
pii edge[maxn];
int res[maxn];
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> q;
    fo(i,1,n - 1)
    {
        int u,v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
        edge[i] = {u,v};
    }
    dfs(1);
    fo(j,1,19) fo(i,1,n) par[i][j] = par[par[i][j - 1]][j - 1];
    fo(i,1,n) t.up(pos[i],tail[i],1);
    fo(i,1,n) res[i] = 1;
    fo(i,1,m)
    {
        int id;
        cin >> id;
        auto [u,v] = edge[id];
        if(pos[u] > pos[v]) swap(u,v);
        u = find(u);
        if(!on[id])
        {
            res[u] = res[u] + res[v] - save[id];
            t.up(pos[v],tail[v],-1);
        }
        else
        {
            res[v] = save[id] = res[u];
            t.up(pos[v],tail[v],1);
        }
        on[id] = 1 - on[id];
    }
    fo(i,1,q)
    {
        int x;
        cin >> x;
        cout << res[find(x)];en;
    }
}

Compilation message

synchronization.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main()
      | ^~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34908 KB Output is correct
2 Correct 6 ms 34908 KB Output is correct
3 Correct 6 ms 34996 KB Output is correct
4 Correct 7 ms 35028 KB Output is correct
5 Correct 6 ms 34904 KB Output is correct
6 Correct 7 ms 35260 KB Output is correct
7 Correct 18 ms 38492 KB Output is correct
8 Correct 17 ms 38448 KB Output is correct
9 Correct 19 ms 38492 KB Output is correct
10 Correct 144 ms 57772 KB Output is correct
11 Correct 150 ms 57472 KB Output is correct
12 Correct 207 ms 60228 KB Output is correct
13 Correct 73 ms 59080 KB Output is correct
14 Correct 102 ms 56732 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 58756 KB Output is correct
2 Correct 92 ms 56896 KB Output is correct
3 Correct 84 ms 58872 KB Output is correct
4 Correct 89 ms 58708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34908 KB Output is correct
2 Correct 6 ms 34908 KB Output is correct
3 Correct 6 ms 34908 KB Output is correct
4 Correct 6 ms 34908 KB Output is correct
5 Correct 6 ms 34980 KB Output is correct
6 Correct 7 ms 35160 KB Output is correct
7 Correct 20 ms 39000 KB Output is correct
8 Correct 234 ms 61012 KB Output is correct
9 Correct 247 ms 61008 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 64080 KB Output is correct
2 Correct 137 ms 63060 KB Output is correct
3 Correct 126 ms 64584 KB Output is correct
4 Correct 134 ms 63140 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34908 KB Output is correct
2 Correct 5 ms 34908 KB Output is correct
3 Correct 5 ms 34908 KB Output is correct
4 Correct 5 ms 35064 KB Output is correct
5 Correct 7 ms 35260 KB Output is correct
6 Correct 20 ms 38492 KB Output is correct
7 Correct 174 ms 61544 KB Output is correct
8 Correct 235 ms 62804 KB Output is correct
9 Correct 98 ms 62152 KB Output is correct
10 Correct 120 ms 59220 KB Output is correct
11 Correct 115 ms 61648 KB Output is correct
12 Correct 120 ms 63112 KB Output is correct
13 Correct 129 ms 63256 KB Output is correct