Submission #1119120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119120		kiethm07	Synchronization (JOI13_synchronization)	C++11	100 / 100	283 ms	26260 KiB

synchronization

#include <bits/stdc++.h>

#define pii pair<int,int>
#define pli pair<long long,int>
#define plii pair<long long,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define all(x) x.begin(),x.end()
#define compact(x) x.erase(unique(all(x)),x.end())
#define pb(x) push_back(x)

using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
const ll linf = 1e16;
const double PI = acos(-1);
const int N = 1e5 + 5;
const int LOG = 17;

class BIT{
private:
    vector<int> bit;
    int n;
public:
    BIT(int m){
        n = m + 5;
        bit.resize(n + 5,0);
    }
    void update(int i,int v){
        for (i; i <= n; i += i & (-i)) bit[i] += v;
    }
    void update(int l,int r,int v){
        update(l,v);
        update(r + 1,-v);
    }
    int get(int i){
        int res = 0;
        for (i; i > 0; i -= i & (-i)) res += bit[i];
        return res;
    }
};

struct edge{
    int u,v,w;
    edge(){}
    edge(int a,int b,int c){
        u = a,v = b,w = c;
    }
};

edge e[N];
int pa[N][LOG];
int n,m,q;
vector<int> a[N];
int tin[N], tout[N], curTime;
int h[N];
BIT bit(N);
bool active[N];
int val[N];

void dfs(int u,int p){
    tin[u] = ++curTime;
    val[u] = 1;
    for (int i = 1; (1 << i) <= h[u]; i++){
        pa[u][i] = pa[pa[u][i-1]][i-1];
    }
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i];
        if (v == p) continue;
        h[v] = h[u] + 1;
        pa[v][0] = u;
        dfs(v,u);
    }
    tout[u] = curTime;
}

int getNode(int u){
    int cur = 0;
    int tmp = bit.get(tin[u]);
    for (int i = LOG - 1; i >= 0; i--){
        if (pa[u][i] == 0) continue;
        if (cur + (1 << i) != (tmp - bit.get(tin[pa[u][i]]))) continue;
        cur += 1 << i;
        u = pa[u][i];
    }
    return u;
}

void query(int id){
    int u = e[id].u;
    int v = e[id].v;
    int f = getNode(u);
    int tmp = val[f] + val[v] - e[id].w;
    val[f] = val[v] = e[id].w = tmp;
    if (active[id]){
        bit.update(tin[v],tout[v],-1);
    }
    else bit.update(tin[v],tout[v],1);
    active[id] ^= 1;
}

int main(){
    #define TEXT "synchronization"
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen(TEXT".inp","r")){
        freopen(TEXT".inp","r",stdin);
        freopen(TEXT".out","w",stdout);
    }
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
        e[i] = edge(u,v,0);
    }
    dfs(1,-1);
    for (int i = 1; i < n; i++){
        if (tin[e[i].u] > tin[e[i].v]) swap(e[i].u, e[i].v);
    }
    vector<int> updateList(m), queryList(q);
    for (int &i : updateList) cin >> i;
    for (int &i : queryList) cin >> i;
    for (int i = 0; i < m; i++){
        int id = updateList[i];
        query(id);
    }
    for (int i = 0; i < q; i++){
        int u = queryList[i];
        int f = getNode(u);
        cout << val[f] << "\n";
    }
    return 0;
}

Compilation message (stderr)

synchronization.cpp: In member function 'void BIT::update(int, int)':
synchronization.cpp:36:14: warning: statement has no effect [-Wunused-value]
   36 |         for (i; i <= n; i += i & (-i)) bit[i] += v;
      |              ^
synchronization.cpp: In member function 'int BIT::get(int)':
synchronization.cpp:44:14: warning: statement has no effect [-Wunused-value]
   44 |         for (i; i > 0; i -= i & (-i)) res += bit[i];
      |              ^
synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(TEXT".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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