Submission #387469

#	Time	Username	Problem	Language	Result	Execution time	Memory
387469		jeroenodb	Synchronization (JOI13_synchronization)	C++14	100 / 100	302 ms	27796 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5;
const ll oo = 1e18;
namespace hld {
    int n;
    int chain[mxN],sz[mxN], parent[mxN],in[mxN], info[mxN], uploaded[mxN] = {};
    // vector<edge> edges;
    vi adj[mxN];
    vector<pi> edges;
    set<int,greater<int>> sets[mxN];
    int cnt = 0;
    void dfs(int at=0, int path=-1) {
        int min = in[at] = cnt++;
        chain[min] = (path==-1)?min:path;
        sets[chain[min]].insert(min);

        if(adj[at].empty()) 
            return;
        int mx=-2,heavy = -1;
        for(int to: adj[at]) {
            if(sz[to] > mx) {
                mx = sz[to];
                heavy=to;
            } 
        }
        assert(heavy!=-1);
        parent[cnt] = min;
        dfs(heavy,chain[min]);
        for(int to: adj[at]) {
            if(to!=heavy) {
                parent[cnt] = min;
                dfs(to);
            }
        }
    }
    void addedge(int a,int b) {
        // edges.push_back({a,b,c});
        adj[a].push_back(b);
        adj[b].push_back(a);
        edges.emplace_back(a,b);
    }
    void init(int nn) {
        n=nn;
        fill(sz, sz+n, 1);
        fill(parent, parent+n,-1);
        fill(info, info+n,1);
        vector<pi> q; q.reserve(n); q.emplace_back(0,-1);
        // Graph must be a tree
        // Do a bfs on nodes
        for(int i=0;i<(int)q.size();++i) {
            int at,from; tie(at,from) = q[i];
            for(int j=0;j<(int)adj[at].size();++j) {
                int& to = adj[at][j];
                if(to!=from) {
                    q.emplace_back(to,at);
                } else {
                    swap(to,adj[at].back());
                    adj[at].pop_back();
                    j--;
                }
            }
        }
        assert(q.size()==n);
        for(int i=n-1;i>=0;--i) {
            int at = q[i].first;
            for(int to: adj[at]) 
                sz[at]+=sz[to];
        }
        dfs();
    }
    auto root(int at) { // at = in[node]
        while(chain[at]!=0) {
            if(!sets[chain[at]].empty() and *sets[chain[at]].rbegin() <= at) {
                break;
            }
            at = parent[chain[at]];
        }
        return *sets[chain[at]].lower_bound(at);
    }
    bool update(int i) {
        auto [iter,good] = sets[chain[i]].insert(i);
        if(!good) {
            sets[chain[i]].erase(iter);
        }
        return good;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,q; cin >> n >> m >> q;
    for(int i=0;i<n-1;++i) {
        int a,b; cin >> a >> b;
        hld::addedge(a-1,b-1);
    }
    hld::init(n);
    
    while(m--) {
        using namespace hld;
        int eid; cin >> eid; eid--;
        auto [a,b] = edges[eid];
        a = in[a], b = in[b];
        if(a>b) swap(a,b);
        if(!update(b)) {
            info[root(a)]+=info[b]-uploaded[b];
        } else {
            uploaded[b] = info[b] = info[root(a)];
        }
    }

    while(q--) {
        using namespace hld;
        int c; cin >> c; c = in[c-1];
        cout << info[root(c)] << '\n';
    }
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from synchronization.cpp:1:
synchronization.cpp: In function 'void hld::init(int)':
synchronization.cpp:69:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         assert(q.size()==n);
      |                ~~~~~~~~^~~
synchronization.cpp: In function 'bool hld::update(int)':
synchronization.cpp:87:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         auto [iter,good] = sets[chain[i]].insert(i);
      |              ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:108:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |         auto [a,b] = edges[eid];
      |              ^

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