oj.uz

Submission #1114956

# Submission time Handle Problem Language Result Execution time Memory
1114956 2024-11-19T20:40:35 Z HoriaHaivas Inside information (BOI21_servers) C++14
50 / 100
 406 ms 47292 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;
};


///aici e problema
///intervalele sunt ele cu l+1 fata de subarb, dar daca sunt asa, atunci vreau toate updateurile inainte
bool cmp(idk a, idk b)
{
    if (a.l!=b.l)
    return a.l>b.l;
    else
    return a.type<b.type;
}

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:243:15: warning: unused variable 'j' [-Wunused-variable]
  243 |     int n,k,i,j;
      |               ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21992 KB Output is correct
2 Correct 34 ms 23124 KB Output is correct
3 Correct 41 ms 22096 KB Output is correct
4 Correct 34 ms 23120 KB Output is correct
5 Correct 32 ms 23368 KB Output is correct
6 Correct 62 ms 23156 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21992 KB Output is correct
2 Correct 34 ms 23124 KB Output is correct
3 Correct 41 ms 22096 KB Output is correct
4 Correct 34 ms 23120 KB Output is correct
5 Correct 32 ms 23368 KB Output is correct
6 Correct 62 ms 23156 KB Output is correct
7 Incorrect 24 ms 21948 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 25 ms 21996 KB Output is correct
2 Correct 255 ms 42160 KB Output is correct
3 Correct 257 ms 41680 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 21996 KB Output is correct
2 Correct 255 ms 42160 KB Output is correct
3 Correct 257 ms 41680 KB Output is correct
4 Incorrect 27 ms 20804 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 24 ms 20716 KB Output is correct
2 Correct 190 ms 34376 KB Output is correct
3 Correct 202 ms 34832 KB Output is correct
4 Correct 402 ms 47204 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 20716 KB Output is correct
2 Correct 190 ms 34376 KB Output is correct
3 Correct 202 ms 34832 KB Output is correct
4 Correct 402 ms 47204 KB Output is correct
5 Incorrect 22 ms 21876 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 20900 KB Output is correct
2 Correct 369 ms 36324 KB Output is correct
3 Correct 182 ms 31816 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 20900 KB Output is correct
2 Correct 369 ms 36324 KB Output is correct
3 Correct 182 ms 31816 KB Output is correct
4 Incorrect 25 ms 22064 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 22 ms 22188 KB Output is correct
2 Correct 190 ms 34416 KB Output is correct
3 Correct 171 ms 34380 KB Output is correct
4 Correct 370 ms 47204 KB Output is correct
5 Correct 21 ms 21996 KB Output is correct
6 Correct 354 ms 36280 KB Output is correct
7 Correct 174 ms 31816 KB Output is correct
8 Correct 169 ms 32072 KB Output is correct
9 Correct 183 ms 32388 KB Output is correct
10 Correct 382 ms 40280 KB Output is correct
11 Correct 406 ms 40128 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 22188 KB Output is correct
2 Correct 190 ms 34416 KB Output is correct
3 Correct 171 ms 34380 KB Output is correct
4 Correct 370 ms 47204 KB Output is correct
5 Correct 21 ms 21996 KB Output is correct
6 Correct 354 ms 36280 KB Output is correct
7 Correct 174 ms 31816 KB Output is correct
8 Correct 169 ms 32072 KB Output is correct
9 Correct 183 ms 32388 KB Output is correct
10 Correct 382 ms 40280 KB Output is correct
11 Correct 406 ms 40128 KB Output is correct
12 Incorrect 22 ms 22020 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 20 ms 21996 KB Output is correct
2 Correct 32 ms 23188 KB Output is correct
3 Correct 38 ms 22088 KB Output is correct
4 Correct 33 ms 23288 KB Output is correct
5 Correct 30 ms 23400 KB Output is correct
6 Correct 65 ms 23112 KB Output is correct
7 Correct 23 ms 22008 KB Output is correct
8 Correct 233 ms 41904 KB Output is correct
9 Correct 230 ms 41792 KB Output is correct
10 Correct 20 ms 22180 KB Output is correct
11 Correct 190 ms 34376 KB Output is correct
12 Correct 185 ms 34472 KB Output is correct
13 Correct 400 ms 47292 KB Output is correct
14 Correct 22 ms 22176 KB Output is correct
15 Correct 354 ms 36280 KB Output is correct
16 Correct 178 ms 31816 KB Output is correct
17 Correct 170 ms 31984 KB Output is correct
18 Correct 217 ms 32524 KB Output is correct
19 Correct 381 ms 40128 KB Output is correct
20 Correct 389 ms 40032 KB Output is correct
21 Correct 325 ms 39804 KB Output is correct
22 Correct 285 ms 36516 KB Output is correct
23 Correct 185 ms 31656 KB Output is correct
24 Correct 192 ms 31560 KB Output is correct
25 Correct 258 ms 38072 KB Output is correct
26 Correct 170 ms 31308 KB Output is correct
27 Correct 162 ms 32288 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21996 KB Output is correct
2 Correct 32 ms 23188 KB Output is correct
3 Correct 38 ms 22088 KB Output is correct
4 Correct 33 ms 23288 KB Output is correct
5 Correct 30 ms 23400 KB Output is correct
6 Correct 65 ms 23112 KB Output is correct
7 Correct 23 ms 22008 KB Output is correct
8 Correct 233 ms 41904 KB Output is correct
9 Correct 230 ms 41792 KB Output is correct
10 Correct 20 ms 22180 KB Output is correct
11 Correct 190 ms 34376 KB Output is correct
12 Correct 185 ms 34472 KB Output is correct
13 Correct 400 ms 47292 KB Output is correct
14 Correct 22 ms 22176 KB Output is correct
15 Correct 354 ms 36280 KB Output is correct
16 Correct 178 ms 31816 KB Output is correct
17 Correct 170 ms 31984 KB Output is correct
18 Correct 217 ms 32524 KB Output is correct
19 Correct 381 ms 40128 KB Output is correct
20 Correct 389 ms 40032 KB Output is correct
21 Correct 325 ms 39804 KB Output is correct
22 Correct 285 ms 36516 KB Output is correct
23 Correct 185 ms 31656 KB Output is correct
24 Correct 192 ms 31560 KB Output is correct
25 Correct 258 ms 38072 KB Output is correct
26 Correct 170 ms 31308 KB Output is correct
27 Correct 162 ms 32288 KB Output is correct
28 Incorrect 23 ms 22072 KB Extra information in the output file
29 Halted 0 ms 0 KB -