oj.uz

Submission #1114953

# Submission time Handle Problem Language Result Execution time Memory
1114953 2024-11-19T20:36:30 Z HoriaHaivas Inside information (BOI21_servers) C++14
50 / 100
 433 ms 47348 KB 
/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

struct operatie
{
    char type;
    int u;
    int v;
    int moment;
    int ans;
};

struct idk
{
    int type;///0 - update, 1 - query
    int l;
    int r;
    int who;
};

bool cmp(idk a, idk b)
{
    if (a.l!=b.l)
    return a.l>b.l;
    else
    return a.r<b.r;
}

struct edge
{
    int to;
    int w;
};

vector<idk> events;
operatie q[240005];
vector<operatie> qq[120005];
map<int,pair<int,int>> cresc;
int aib[240005];
vector<edge> nodes[120005];
bool blocked[120005];
int sz[120005];
int maxx;

void update(int idx, int delta)
{
    while (idx<=maxx)
    {
        aib[idx]+=delta;
        idx+=idx&(-idx);
    }
}

int query(int idx)
{
    int ans;
    ans=0;
    while (idx>0)
    {
        ans+=aib[idx];
        idx-=idx&(-idx);
    }
    return ans;
}

void recalc(int node, int parent)
{
    sz[node]=1;
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
        {
            recalc(x.to,node);
            sz[node]+=sz[x.to];
        }
    }
}

int find_centroid(int node, int parent, int compsize)
{
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && sz[x.to]>compsize/2)
        {
            return find_centroid(x.to,node,compsize);
        }
    }
    return node;
}

bool canadd;

void add_cresc(int node, int parent, int first, int last)
{
    cresc[node]= {first,last};
    if (canadd)
    events.push_back({0,first,last,0});
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && x.w>last)
        {
            add_cresc(x.to,node,first,x.w);
        }
    }
}

void rem_cresc(int node, int parent, int first, int last)
{
    cresc[node]= {-1,-1};
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && x.w>last)
        {
            rem_cresc(x.to,node,first,x.w);
        }
    }
}

int globc;

void solve(int node, int parent, int first, int last)
{
    for (auto x : qq[node])
    {
        if (x.type=='Q')
        {
            if (x.u==x.v)
                q[x.moment].ans|=1;
            else if (x.u==globc && first<x.moment)
                q[x.moment].ans|=1;
            else if (cresc.find(x.u)==cresc.end() || (cresc[x.u].first==-1 && cresc[x.u].second==-1))
                q[x.moment].ans|=0;
            else if (cresc[x.u].first>first && cresc[x.u].second<x.moment)
                q[x.moment].ans|=1;
        }
        else
        {
            events.push_back({1,first+1,x.moment-1,x.moment});
        }
    }
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && x.w<last)
        {
            solve(x.to,node,first,x.w);
        }
    }
}

void cd(int node)
{
    int centroid;
    cresc.clear();
    events.clear();
    recalc(node,-1);
    centroid=find_centroid(node,-1,sz[node]);
    globc=centroid;
    blocked[centroid]=1;
    canadd=1;
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            add_cresc(x.to,centroid,x.w,x.w);
        }
    }
    for (auto x : qq[centroid])
    {
        if (x.type=='Q')
        {
            if (x.u==x.v)
                q[x.moment].ans|=1;
            else if (cresc.find(x.u)==cresc.end() || (cresc[x.u].first==-1 && cresc[x.u].second==-1))
                q[x.moment].ans|=0;
            else if (cresc[x.u].second<x.moment)
                q[x.moment].ans|=1;
        }
        else
        {
            events.push_back({1,1,x.moment-1,x.moment});
        }
    }
    canadd=0;
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            rem_cresc(x.to,centroid,x.w,x.w);
            solve(x.to,centroid,x.w,x.w);
            add_cresc(x.to,centroid,x.w,x.w);
        }
    }
    sort(events.begin(),events.end(),cmp);
    for (auto x : events)
    {
        if (x.type==0)
        {
            update(x.r,1);
        }
        else
        {
            q[x.who].ans+=query(x.r)+1;
        }
    }
    for (auto x : events)
    {
        if (x.type==0)
        {
            update(x.r,-1);
        }
    }
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            cd(x.to);
        }
    }
}

signed main()
{
    /*
    ifstream fin("secvp.in");
    ofstream fout("secvp.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k,i,j;
    cin >> n >> k;
    for (i=1; i<=n+k-1; i++)
    {
        cin >> q[i].type;
        q[i].moment=i;
        if (q[i].type=='S')
        {
            cin >> q[i].u >> q[i].v;
            nodes[q[i].u].push_back({q[i].v,i});
            nodes[q[i].v].push_back({q[i].u,i});
        }
        if (q[i].type=='Q')
        {
            cin >> q[i].u >> q[i].v;
            qq[q[i].v].push_back(q[i]);
        }
        if (q[i].type=='C')
        {
            cin >> q[i].u;
            qq[q[i].u].push_back(q[i]);
        }
    }
    maxx=n+k-1;
    cd(1);
    for (i=1; i<=n+k-1; i++)
    {
        if (q[i].type=='Q')
        {
            if (q[i].ans==1)
                cout << "yes\n";
            else
                cout << "no\n";
        }
        else if (q[i].type=='C')
        {
            cout << q[i].ans << "\n";
        }
    }
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:240:15: warning: unused variable 'j' [-Wunused-variable]
  240 |     int n,k,i,j;
      |               ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21996 KB Output is correct
2 Correct 33 ms 23188 KB Output is correct
3 Correct 39 ms 22088 KB Output is correct
4 Correct 32 ms 23112 KB Output is correct
5 Correct 31 ms 23380 KB Output is correct
6 Correct 61 ms 23164 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21996 KB Output is correct
2 Correct 33 ms 23188 KB Output is correct
3 Correct 39 ms 22088 KB Output is correct
4 Correct 32 ms 23112 KB Output is correct
5 Correct 31 ms 23380 KB Output is correct
6 Correct 61 ms 23164 KB Output is correct
7 Incorrect 23 ms 21892 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21996 KB Output is correct
2 Correct 246 ms 41944 KB Output is correct
3 Correct 223 ms 42292 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21996 KB Output is correct
2 Correct 246 ms 41944 KB Output is correct
3 Correct 223 ms 42292 KB Output is correct
4 Incorrect 32 ms 22156 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22004 KB Output is correct
2 Correct 174 ms 34380 KB Output is correct
3 Correct 203 ms 34416 KB Output is correct
4 Correct 417 ms 47348 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22004 KB Output is correct
2 Correct 174 ms 34380 KB Output is correct
3 Correct 203 ms 34416 KB Output is correct
4 Correct 417 ms 47348 KB Output is correct
5 Incorrect 22 ms 22064 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22164 KB Output is correct
2 Correct 364 ms 36324 KB Output is correct
3 Correct 195 ms 31816 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22164 KB Output is correct
2 Correct 364 ms 36324 KB Output is correct
3 Correct 195 ms 31816 KB Output is correct
4 Incorrect 27 ms 22076 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 21996 KB Output is correct
2 Correct 218 ms 34376 KB Output is correct
3 Correct 216 ms 34452 KB Output is correct
4 Correct 420 ms 47288 KB Output is correct
5 Correct 23 ms 21988 KB Output is correct
6 Correct 359 ms 36596 KB Output is correct
7 Correct 206 ms 31804 KB Output is correct
8 Correct 217 ms 32008 KB Output is correct
9 Correct 213 ms 32328 KB Output is correct
10 Correct 396 ms 40136 KB Output is correct
11 Correct 429 ms 40128 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 21996 KB Output is correct
2 Correct 218 ms 34376 KB Output is correct
3 Correct 216 ms 34452 KB Output is correct
4 Correct 420 ms 47288 KB Output is correct
5 Correct 23 ms 21988 KB Output is correct
6 Correct 359 ms 36596 KB Output is correct
7 Correct 206 ms 31804 KB Output is correct
8 Correct 217 ms 32008 KB Output is correct
9 Correct 213 ms 32328 KB Output is correct
10 Correct 396 ms 40136 KB Output is correct
11 Correct 429 ms 40128 KB Output is correct
12 Incorrect 26 ms 20784 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 20816 KB Output is correct
2 Correct 38 ms 23176 KB Output is correct
3 Correct 54 ms 22020 KB Output is correct
4 Correct 35 ms 23120 KB Output is correct
5 Correct 34 ms 23368 KB Output is correct
6 Correct 70 ms 23112 KB Output is correct
7 Correct 23 ms 22080 KB Output is correct
8 Correct 319 ms 41904 KB Output is correct
9 Correct 274 ms 41788 KB Output is correct
10 Correct 23 ms 21988 KB Output is correct
11 Correct 191 ms 34376 KB Output is correct
12 Correct 200 ms 34380 KB Output is correct
13 Correct 385 ms 47288 KB Output is correct
14 Correct 21 ms 22300 KB Output is correct
15 Correct 339 ms 36280 KB Output is correct
16 Correct 153 ms 31816 KB Output is correct
17 Correct 164 ms 32072 KB Output is correct
18 Correct 205 ms 32328 KB Output is correct
19 Correct 419 ms 40128 KB Output is correct
20 Correct 433 ms 40128 KB Output is correct
21 Correct 344 ms 39720 KB Output is correct
22 Correct 299 ms 36520 KB Output is correct
23 Correct 183 ms 31520 KB Output is correct
24 Correct 176 ms 31564 KB Output is correct
25 Correct 284 ms 37884 KB Output is correct
26 Correct 206 ms 31308 KB Output is correct
27 Correct 196 ms 32328 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 20816 KB Output is correct
2 Correct 38 ms 23176 KB Output is correct
3 Correct 54 ms 22020 KB Output is correct
4 Correct 35 ms 23120 KB Output is correct
5 Correct 34 ms 23368 KB Output is correct
6 Correct 70 ms 23112 KB Output is correct
7 Correct 23 ms 22080 KB Output is correct
8 Correct 319 ms 41904 KB Output is correct
9 Correct 274 ms 41788 KB Output is correct
10 Correct 23 ms 21988 KB Output is correct
11 Correct 191 ms 34376 KB Output is correct
12 Correct 200 ms 34380 KB Output is correct
13 Correct 385 ms 47288 KB Output is correct
14 Correct 21 ms 22300 KB Output is correct
15 Correct 339 ms 36280 KB Output is correct
16 Correct 153 ms 31816 KB Output is correct
17 Correct 164 ms 32072 KB Output is correct
18 Correct 205 ms 32328 KB Output is correct
19 Correct 419 ms 40128 KB Output is correct
20 Correct 433 ms 40128 KB Output is correct
21 Correct 344 ms 39720 KB Output is correct
22 Correct 299 ms 36520 KB Output is correct
23 Correct 183 ms 31520 KB Output is correct
24 Correct 176 ms 31564 KB Output is correct
25 Correct 284 ms 37884 KB Output is correct
26 Correct 206 ms 31308 KB Output is correct
27 Correct 196 ms 32328 KB Output is correct
28 Incorrect 27 ms 21892 KB Extra information in the output file
29 Halted 0 ms 0 KB -