oj.uz

Submission #549664

# Submission time Handle Problem Language Result Execution time Memory
549664 2022-04-16T08:40:24 Z fcmalkcin Inside information (BOI21_servers) C++17
100 / 100
 464 ms 53172 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)

const ll maxn=3e5+10 ;
const ll base=3e18;
const ll mod= 1e9+7 ;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

/// have medal in APIO
/// goal 2/8

char p[maxn];
ll x[maxn];
ll y[maxn];
vector<pll> adj[maxn];
ll siz[maxn];
bool dd[maxn];
ll find_siz(ll u,ll par)
{
    siz[u]=1;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        if (to==par||dd[to])
            continue;
        siz[u]+=find_siz(to,u);
    }
    return siz[u];
}
ll find_cen(ll u,ll par,ll siz1)
{
    ll mx=siz1-siz[u];
    for (auto p:adj[u])
    {
        ll to=p.ff;
        if (to==par||dd[to])
            continue;
        mx=max(mx,siz[to]);
        ll h=find_cen(to,u,siz1);
        if (h!=-1)
        {
            return h;
        }
    }
    if (mx*2<=siz1)
        return u;
    return -1;
}
ll fwt[maxn];
ll dd1[maxn];
vector<ll> adjq[maxn];
vector<pll> adjq1[maxn];
ll res[maxn];

bool lf(pll x,pll y)
{
    return x.ss<y.ss;
}
void update(ll x,ll diff)
{
    for (int i=x; i<maxn; i+= i&(-i))
        fwt[i]+=diff;
}
ll get(ll x,ll y)
{
    ll ans=0;
    for (int i=y; i; i-= i&(-i))
        ans+=fwt[i];
    for (int i=x-1; i; i-= i&(-i))
        ans-=fwt[i];
    return ans;
}
void dfsget(ll u,ll par,ll pre,ll mx)
{

    for (auto to:adjq1[u])
    {
        ll id=to.ss;
        ll nxt=to.ff;
        if (dd1[nxt]&&mx<id&&dd1[nxt]<=id)
        {
            res[id]=1;
        }
    }
    for (auto p:adjq[u])
    {
        if (p>=mx)
        {
            res[p]+=get(1,p);
        }
    }
    for (auto p:adj[u])
    {
        ll to=p.ff;
        ll w=p.ss;
        if (dd[to]||to==par)
            continue;
        if (w<pre)
        {
            dfsget(to,u,w,mx);
        }
    }
}
void dfsup(ll u,ll par,ll pre,ll diff,ll t)
{
    update(pre,diff);
    dd1[u]=t*pre;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        ll w=p.ss;
        if (dd[to]||to==par)
            continue;
        if (w>pre)
        {
            dfsup(to,u,w,diff,t);
        }
    }
}

void centroid(ll u)
{
    ll siz=find_siz(u,0);
    sort(adj[u].begin(),adj[u].end(),lf);
    ll cen=find_cen(u,0,siz);
    update(1,1);
    dd1[cen]=1;
    for (int i=adj[cen].size()-1; i>=0; i--)
    {
        ll to=adj[cen][i].ff;
        if (dd[to])
            continue;
        //  cout <<to<<" "<<adj[cen][i].ss<<" wtf"<<endl;
        dfsget(to,cen,adj[cen][i].ss,adj[cen][i].ss);
        dfsup(to,cen,adj[cen][i].ss,1,1);
    }
    dd1[cen]=0;
    update(1,-1);
    for (auto p:adjq[cen])
    {
        res[p]+=get(1,p);
    }
    for (auto to:adjq1[cen])
    {
        ll id=to.ss;
        ll nxt=to.ff;
        if (dd1[nxt]&&dd1[nxt]<=id)
        {
            res[id]=1;
        }
    }
    for (int i=adj[cen].size()-1; i>=0; i--)
    {
        ll to=adj[cen][i].ff;
        if (dd[to])
            continue;
        dfsup(to,cen,adj[cen][i].ss,-1,0);
    }
    dd[cen]=1;
    // exit(0);
    for (auto p:adj[cen])
    {
        ll to=p.ff;
        if (dd[to])
            continue;
        centroid(to);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ll n, k;
    cin>> n>> k;
    k+=n-1;
    for (int i=1; i<=k; i++)
    {
        cin>> p[i];
        if (p[i]=='C')
        {
            cin>> x[i];
            adjq[x[i]].pb(i);
        }
        else
        {
            cin>> x[i]>> y[i];
            if (p[i]=='S')
            {
                adj[x[i]].pb(make_pair(y[i],i));
                adj[y[i]].pb(make_pair(x[i],i));
            }
            else
            {
                if (x[i]!=y[i])
                    adjq1[y[i]].pb(make_pair(x[i],i));
                else
                    res[i]=1;
            }
        }
    }
    centroid(1);
    for (int i=1; i<=k; i++)
    {
        if (p[i]=='C')
        {
            cout <<res[i]+1<<endl;
        }
        else if (p[i]=='Q')
        {
            if (res[i])
                cout <<"yes"<<endl;
            else
                cout <<"no"<<endl;
        }
    }
}

Compilation message

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 28236 KB Output is correct
2 Correct 53 ms 30028 KB Output is correct
3 Correct 45 ms 30228 KB Output is correct
4 Correct 50 ms 30116 KB Output is correct
5 Correct 47 ms 29584 KB Output is correct
6 Correct 46 ms 29984 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 28236 KB Output is correct
2 Correct 53 ms 30028 KB Output is correct
3 Correct 45 ms 30228 KB Output is correct
4 Correct 50 ms 30116 KB Output is correct
5 Correct 47 ms 29584 KB Output is correct
6 Correct 46 ms 29984 KB Output is correct
7 Correct 36 ms 28912 KB Output is correct
8 Correct 48 ms 29580 KB Output is correct
9 Correct 48 ms 29164 KB Output is correct
10 Correct 47 ms 29644 KB Output is correct
11 Correct 54 ms 28984 KB Output is correct
12 Correct 44 ms 28768 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 28320 KB Output is correct
2 Correct 180 ms 43208 KB Output is correct
3 Correct 176 ms 43508 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 28320 KB Output is correct
2 Correct 180 ms 43208 KB Output is correct
3 Correct 176 ms 43508 KB Output is correct
4 Correct 36 ms 29004 KB Output is correct
5 Correct 175 ms 42784 KB Output is correct
6 Correct 110 ms 40128 KB Output is correct
7 Correct 119 ms 40340 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28268 KB Output is correct
2 Correct 278 ms 53024 KB Output is correct
3 Correct 283 ms 53036 KB Output is correct
4 Correct 225 ms 52988 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28268 KB Output is correct
2 Correct 278 ms 53024 KB Output is correct
3 Correct 283 ms 53036 KB Output is correct
4 Correct 225 ms 52988 KB Output is correct
5 Correct 46 ms 29004 KB Output is correct
6 Correct 289 ms 53112 KB Output is correct
7 Correct 237 ms 52916 KB Output is correct
8 Correct 264 ms 52736 KB Output is correct
9 Correct 271 ms 52552 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 28272 KB Output is correct
2 Correct 214 ms 44076 KB Output is correct
3 Correct 228 ms 43644 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 28272 KB Output is correct
2 Correct 214 ms 44076 KB Output is correct
3 Correct 228 ms 43644 KB Output is correct
4 Correct 36 ms 29000 KB Output is correct
5 Correct 238 ms 43924 KB Output is correct
6 Correct 248 ms 43584 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 28248 KB Output is correct
2 Correct 276 ms 53024 KB Output is correct
3 Correct 280 ms 52980 KB Output is correct
4 Correct 222 ms 52944 KB Output is correct
5 Correct 37 ms 29172 KB Output is correct
6 Correct 208 ms 44284 KB Output is correct
7 Correct 224 ms 43644 KB Output is correct
8 Correct 266 ms 43800 KB Output is correct
9 Correct 253 ms 45048 KB Output is correct
10 Correct 274 ms 48172 KB Output is correct
11 Correct 292 ms 47264 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 28248 KB Output is correct
2 Correct 276 ms 53024 KB Output is correct
3 Correct 280 ms 52980 KB Output is correct
4 Correct 222 ms 52944 KB Output is correct
5 Correct 37 ms 29172 KB Output is correct
6 Correct 208 ms 44284 KB Output is correct
7 Correct 224 ms 43644 KB Output is correct
8 Correct 266 ms 43800 KB Output is correct
9 Correct 253 ms 45048 KB Output is correct
10 Correct 274 ms 48172 KB Output is correct
11 Correct 292 ms 47264 KB Output is correct
12 Correct 36 ms 29004 KB Output is correct
13 Correct 286 ms 52876 KB Output is correct
14 Correct 236 ms 52788 KB Output is correct
15 Correct 274 ms 52644 KB Output is correct
16 Correct 266 ms 52532 KB Output is correct
17 Correct 36 ms 29024 KB Output is correct
18 Correct 233 ms 43904 KB Output is correct
19 Correct 235 ms 43572 KB Output is correct
20 Correct 260 ms 44296 KB Output is correct
21 Correct 258 ms 45016 KB Output is correct
22 Correct 295 ms 46952 KB Output is correct
23 Correct 453 ms 47460 KB Output is correct
24 Correct 388 ms 46520 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28180 KB Output is correct
2 Correct 48 ms 30076 KB Output is correct
3 Correct 44 ms 30188 KB Output is correct
4 Correct 46 ms 30068 KB Output is correct
5 Correct 47 ms 29524 KB Output is correct
6 Correct 47 ms 30156 KB Output is correct
7 Correct 37 ms 29280 KB Output is correct
8 Correct 169 ms 43336 KB Output is correct
9 Correct 166 ms 43124 KB Output is correct
10 Correct 37 ms 29132 KB Output is correct
11 Correct 264 ms 53004 KB Output is correct
12 Correct 270 ms 53172 KB Output is correct
13 Correct 223 ms 52992 KB Output is correct
14 Correct 37 ms 29164 KB Output is correct
15 Correct 214 ms 44160 KB Output is correct
16 Correct 235 ms 43648 KB Output is correct
17 Correct 236 ms 43852 KB Output is correct
18 Correct 250 ms 45060 KB Output is correct
19 Correct 278 ms 48216 KB Output is correct
20 Correct 274 ms 47296 KB Output is correct
21 Correct 192 ms 43780 KB Output is correct
22 Correct 189 ms 43688 KB Output is correct
23 Correct 203 ms 44492 KB Output is correct
24 Correct 208 ms 44544 KB Output is correct
25 Correct 280 ms 47936 KB Output is correct
26 Correct 259 ms 42296 KB Output is correct
27 Correct 254 ms 42064 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28180 KB Output is correct
2 Correct 48 ms 30076 KB Output is correct
3 Correct 44 ms 30188 KB Output is correct
4 Correct 46 ms 30068 KB Output is correct
5 Correct 47 ms 29524 KB Output is correct
6 Correct 47 ms 30156 KB Output is correct
7 Correct 37 ms 29280 KB Output is correct
8 Correct 169 ms 43336 KB Output is correct
9 Correct 166 ms 43124 KB Output is correct
10 Correct 37 ms 29132 KB Output is correct
11 Correct 264 ms 53004 KB Output is correct
12 Correct 270 ms 53172 KB Output is correct
13 Correct 223 ms 52992 KB Output is correct
14 Correct 37 ms 29164 KB Output is correct
15 Correct 214 ms 44160 KB Output is correct
16 Correct 235 ms 43648 KB Output is correct
17 Correct 236 ms 43852 KB Output is correct
18 Correct 250 ms 45060 KB Output is correct
19 Correct 278 ms 48216 KB Output is correct
20 Correct 274 ms 47296 KB Output is correct
21 Correct 192 ms 43780 KB Output is correct
22 Correct 189 ms 43688 KB Output is correct
23 Correct 203 ms 44492 KB Output is correct
24 Correct 208 ms 44544 KB Output is correct
25 Correct 280 ms 47936 KB Output is correct
26 Correct 259 ms 42296 KB Output is correct
27 Correct 254 ms 42064 KB Output is correct
28 Correct 35 ms 28932 KB Output is correct
29 Correct 48 ms 29624 KB Output is correct
30 Correct 49 ms 29184 KB Output is correct
31 Correct 50 ms 29688 KB Output is correct
32 Correct 49 ms 28928 KB Output is correct
33 Correct 42 ms 28748 KB Output is correct
34 Correct 35 ms 28936 KB Output is correct
35 Correct 163 ms 42732 KB Output is correct
36 Correct 111 ms 40212 KB Output is correct
37 Correct 119 ms 40344 KB Output is correct
38 Correct 37 ms 29004 KB Output is correct
39 Correct 265 ms 52940 KB Output is correct
40 Correct 241 ms 52836 KB Output is correct
41 Correct 270 ms 52568 KB Output is correct
42 Correct 270 ms 52468 KB Output is correct
43 Correct 35 ms 29004 KB Output is correct
44 Correct 233 ms 43912 KB Output is correct
45 Correct 239 ms 43632 KB Output is correct
46 Correct 251 ms 44308 KB Output is correct
47 Correct 259 ms 44964 KB Output is correct
48 Correct 294 ms 46956 KB Output is correct
49 Correct 464 ms 47436 KB Output is correct
50 Correct 400 ms 46592 KB Output is correct
51 Correct 133 ms 41492 KB Output is correct
52 Correct 114 ms 41308 KB Output is correct
53 Correct 115 ms 40732 KB Output is correct
54 Correct 116 ms 41344 KB Output is correct
55 Correct 125 ms 41124 KB Output is correct
56 Correct 204 ms 43248 KB Output is correct
57 Correct 225 ms 46012 KB Output is correct
58 Correct 321 ms 42344 KB Output is correct
59 Correct 267 ms 42060 KB Output is correct