oj.uz

Submission #887527

# Submission time Handle Problem Language Result Execution time Memory
887527 2023-12-14T17:04:29 Z AgentPengin Synchronization (JOI13_synchronization) C++17
100 / 100
 224 ms 25356 KB 
/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 1e5 + 5;

int n,m,q;
vector<int> adj[MAXN];
pair<int,int> edges[MAXN << 1];
bool active[MAXN];

int info[MAXN],last_sync[MAXN];

int times = 1,tin[MAXN],tout[MAXN];
int up[MAXN][20];

void dfs(int u = 1,int p = 0) {
	up[u][0] = p;
	for (int i = 1;i < 20 && up[u][i - 1];i++) {
		up[u][i] = up[up[u][i - 1]][i - 1];
	}
	info[u] = 1;
	tin[u] = times++;
	for (auto v : adj[u]) if (v != p) dfs(v,u);
	tout[u] = times;
}

int bit[MAXN];

void update(int x,int val) {
	for (;x <= n;x += x&-x) bit[x] += val;
}

int get(int x) {
	int res = 0;
	for (;x;x-=x&-x) res += bit[x];
	return res;
}

int find_anc(int u) {
	int lca = u;
	for (int i = 19; ~ i;i--) {
		if (up[lca][i] && get(tin[up[lca][i]]) == get(tin[u])) lca = up[lca][i];
	}
	return lca;
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (ifstream(NAME".inp")) {
        freopen(NAME".inp","r",stdin);
        freopen(NAME".out","w",stdout);
    }
    cin >> n >> m >> q;
    for (int i = 1;i < n;i++) {
    	cin >> edges[i].fi >> edges[i].se;
    	adj[edges[i].fi].push_back(edges[i].se);
    	adj[edges[i].se].push_back(edges[i].fi);
    }
    dfs();
    for (int i = 1;i <= n;i++) {
    	update(tin[i],-1);
    	update(tout[i],1);
    }
    while(m--) {
    	int x; cin >> x;
    	int u = edges[x].fi,v = edges[x].se;
    	if (up[u][0] == v) swap(u,v);
    	if (active[x]) {
    		info[v] = last_sync[v] = info[find_anc(u)];
    		update(tin[v],-1);
    		update(tout[v],1);
    	} else {
    		info[find_anc(u)] += info[v] - last_sync[v];
    		update(tin[v],1);
    		update(tout[v],-1);
    	}
    	active[x] = !active[x];
    }
	while(q--) {
		int x;
		cin >> x;
		cout << info[find_anc(x)] << EL;
	}
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
// agent pengin wants to take apio (with anya-san)

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(NAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(NAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9964 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 9 ms 10508 KB Output is correct
8 Correct 9 ms 10332 KB Output is correct
9 Correct 9 ms 10424 KB Output is correct
10 Correct 96 ms 19764 KB Output is correct
11 Correct 96 ms 19540 KB Output is correct
12 Correct 158 ms 24148 KB Output is correct
13 Correct 46 ms 19544 KB Output is correct
14 Correct 66 ms 19012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 21844 KB Output is correct
2 Correct 57 ms 21652 KB Output is correct
3 Correct 75 ms 23632 KB Output is correct
4 Correct 78 ms 23724 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 2 ms 9964 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9964 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 10392 KB Output is correct
7 Correct 15 ms 10844 KB Output is correct
8 Correct 213 ms 25356 KB Output is correct
9 Correct 224 ms 25116 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 24980 KB Output is correct
2 Correct 125 ms 24800 KB Output is correct
3 Correct 126 ms 24848 KB Output is correct
4 Correct 125 ms 24912 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9964 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9964 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 4 ms 9980 KB Output is correct
6 Correct 12 ms 10588 KB Output is correct
7 Correct 152 ms 20484 KB Output is correct
8 Correct 201 ms 24912 KB Output is correct
9 Correct 63 ms 20680 KB Output is correct
10 Correct 85 ms 20308 KB Output is correct
11 Correct 78 ms 23120 KB Output is correct
12 Correct 86 ms 22968 KB Output is correct
13 Correct 137 ms 24824 KB Output is correct