oj.uz

답안 #528892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528892 2022-02-21T17:05:30 Z ParsaEs Inside information (BOI21_servers) C++14
0 / 100
 98 ms 25348 KB 
//InTheNameOfGOD
//PRS;)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define X first
#define Y second
using namespace std;
typedef int ll;
typedef pair<ll,ll> pi;
const ll inf = 2e9, xn = 3e5 + 5;
vector<pi> g[xn], qg[xn];
vector<ll> vc[xn];
ll ans[xn], f[xn], sz[xn], t[xn];
bool vis[xn];
void sdfs(ll v, ll p)
{
    sz[v] = 1;
    for(pi u : g[v]) if(u.X != p && !vis[u.X])
	{
        sdfs(u.X, v);
		sz[v] += sz[u.X];
    }
}
ll gc(ll v, ll p, ll m)
{
    ll mx = 0;
    for(pi u : g[v]) if(u.X != p && !vis[u.X] && sz[mx] < sz[u.X]) mx = u.X;
    if((max(sz[mx], m - sz[v]) << 1) <= m) return v;
    return gc(mx, v, m);
}
inline ll get(ll v)
{
	ll ret = 0;
	for(; v; v -= v & -v) ret += f[v];
	return ret;
}
inline void upd(ll v, ll x)
{
    for(; v < xn; v += v & -v) f[v] += x;
}
void idfs(ll v, ll p, ll ls)
{
	upd(ls, 1);
    t[v] = ls;
    for(pi u : g[v]) if(u.X != p && !vis[u.X] && ls <= u.Y) idfs(u.X, v, u.Y);
}
void odfs(ll v, ll p, ll ls)
{
	upd(ls, -1);
    t[v] = inf;
    for(pi u : g[v]) if(u.X != p && !vis[u.X] && ls <= u.Y) odfs(u.X, v, u.Y);
}
inline void sa(ll v)
{
    for(ll i : vc[v]) ans[i] += get(i);
    for(pi u : qg[v]) if(t[u.X] <= u.Y) ans[u.Y] = -1;
}
void pdfs(ll v, ll p, ll ls)
{
    sa(v);
    for(pi u : g[v]) if(u.X != p && !vis[u.X] && u.Y <= ls) pdfs(u.X, v, u.Y);
}
void doj(ll v, ll p)
{
    sdfs(v, 0);
	ll cen = gc(v, 0, sz[v]);
    sort(g[cen].begin(), g[cen].end()), idfs(cen, 0, 1), sa(cen);
    for(pi u : g[cen]) if(u.X != p && !vis[u.X])
	{
        odfs(u.X, cen, u.Y);
        upd(t[cen], -1);
		t[cen] = u.Y;
        upd(t[cen], 1), pdfs(u.X, cen, u.Y);
    }
    vis[cen] = 1;
	upd(t[cen], -1);
	t[cen] = inf;
    for(pi u : g[cen]) if(u.X != p && !vis[u.X]) doj(u.X, cen);
}
int main()
{
    ll n, q;
    cin >> n >> q;
	q += n - 1;
    for(ll i = 1; i <= q; i++)
	{
		ll v, u;
		char op;
		cin >> op >> v;
		if(op == 'Q')
		{
			cin >> u;
			ans[i] = -2;
            qg[u].push_back({v, i});
		}
		else if(op == 'C')
		{
			vc[v].push_back(i);
			ans[i] = 0;
		}
        else
		{
			cin >> u;
            g[v].push_back({u, i}), g[u].push_back({v, i});
            ans[i] = -69;
        }
    }
    memset(t, 63, sizeof t), doj(1, 0);
    for(ll i = 1; i <= q; i++) if(ans[i] != -69)
	{
        if(ans[i] >= 0)
		{
			cout << ans[i] << '\n';
			continue;
		}
        if(ans[i] == -2) cout << "no\n";
        else cout << "yes\n";
    }
    return 0;
}

Subtask #1
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 61 ms 25252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 61 ms 25252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 76 ms 25328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 76 ms 25328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 25312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 25312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 25284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 25284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 98 ms 25348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 98 ms 25348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 25260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 25260 KB Output isn't correct
2 Halted 0 ms 0 KB -