oj.uz

Submission #1115207

# Submission time Handle Problem Language Result Execution time Memory
1115207 2024-11-20T08:37:00 Z HoriaHaivas Inside information (BOI21_servers) C++14
52.5 / 100
 405 ms 50532 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.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
        {
            if (cresc.find(q[x.who].u)==cresc.end() || (cresc[q[x.who].u].first==-1 && cresc[q[x.who].u].second==-1))
                q[x.who].ans+=0;
            else if (cresc[q[x.who].u].second<=x.r)
                q[x.who].ans+=1;
            q[x.who].ans+=query(x.r);
        }
    }
    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;
            q[i].ans=1;
            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:244:15: warning: unused variable 'j' [-Wunused-variable]
  244 |     int n,k,i,j;
      |               ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22764 KB Output is correct
2 Correct 36 ms 24504 KB Output is correct
3 Correct 42 ms 22088 KB Output is correct
4 Correct 36 ms 24652 KB Output is correct
5 Correct 33 ms 24552 KB Output is correct
6 Correct 67 ms 24648 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22764 KB Output is correct
2 Correct 36 ms 24504 KB Output is correct
3 Correct 42 ms 22088 KB Output is correct
4 Correct 36 ms 24652 KB Output is correct
5 Correct 33 ms 24552 KB Output is correct
6 Correct 67 ms 24648 KB Output is correct
7 Incorrect 26 ms 22924 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 26 ms 22008 KB Output is correct
2 Correct 225 ms 45048 KB Output is correct
3 Correct 222 ms 45136 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 22008 KB Output is correct
2 Correct 225 ms 45048 KB Output is correct
3 Correct 222 ms 45136 KB Output is correct
4 Correct 24 ms 22924 KB Output is correct
5 Correct 237 ms 50532 KB Output is correct
6 Correct 171 ms 48320 KB Output is correct
7 Correct 191 ms 48632 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21972 KB Output is correct
2 Correct 164 ms 37776 KB Output is correct
3 Correct 212 ms 37708 KB Output is correct
4 Correct 383 ms 47544 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21972 KB Output is correct
2 Correct 164 ms 37776 KB Output is correct
3 Correct 212 ms 37708 KB Output is correct
4 Correct 383 ms 47544 KB Output is correct
5 Incorrect 23 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 23192 KB Output is correct
2 Correct 350 ms 39952 KB Output is correct
3 Correct 180 ms 31832 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23192 KB Output is correct
2 Correct 350 ms 39952 KB Output is correct
3 Correct 180 ms 31832 KB Output is correct
4 Incorrect 26 ms 22860 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 25 ms 22756 KB Output is correct
2 Correct 203 ms 37816 KB Output is correct
3 Correct 206 ms 37704 KB Output is correct
4 Correct 387 ms 50104 KB Output is correct
5 Correct 24 ms 23020 KB Output is correct
6 Correct 347 ms 39868 KB Output is correct
7 Correct 170 ms 35144 KB Output is correct
8 Correct 187 ms 33848 KB Output is correct
9 Correct 194 ms 35656 KB Output is correct
10 Correct 382 ms 43424 KB Output is correct
11 Correct 405 ms 43500 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22756 KB Output is correct
2 Correct 203 ms 37816 KB Output is correct
3 Correct 206 ms 37704 KB Output is correct
4 Correct 387 ms 50104 KB Output is correct
5 Correct 24 ms 23020 KB Output is correct
6 Correct 347 ms 39868 KB Output is correct
7 Correct 170 ms 35144 KB Output is correct
8 Correct 187 ms 33848 KB Output is correct
9 Correct 194 ms 35656 KB Output is correct
10 Correct 382 ms 43424 KB Output is correct
11 Correct 405 ms 43500 KB Output is correct
12 Incorrect 24 ms 22832 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 24 ms 21988 KB Output is correct
2 Correct 36 ms 24528 KB Output is correct
3 Correct 42 ms 23368 KB Output is correct
4 Correct 39 ms 24136 KB Output is correct
5 Correct 32 ms 23376 KB Output is correct
6 Correct 63 ms 23160 KB Output is correct
7 Correct 27 ms 23012 KB Output is correct
8 Correct 264 ms 43952 KB Output is correct
9 Correct 246 ms 45116 KB Output is correct
10 Correct 23 ms 22764 KB Output is correct
11 Correct 194 ms 37704 KB Output is correct
12 Correct 208 ms 36280 KB Output is correct
13 Correct 401 ms 47288 KB Output is correct
14 Correct 25 ms 23020 KB Output is correct
15 Correct 349 ms 39844 KB Output is correct
16 Correct 191 ms 35144 KB Output is correct
17 Correct 164 ms 32072 KB Output is correct
18 Correct 156 ms 32584 KB Output is correct
19 Correct 361 ms 42172 KB Output is correct
20 Correct 346 ms 43348 KB Output is correct
21 Correct 274 ms 44072 KB Output is correct
22 Correct 243 ms 39844 KB Output is correct
23 Correct 174 ms 34672 KB Output is correct
24 Correct 183 ms 31560 KB Output is correct
25 Correct 261 ms 40904 KB Output is correct
26 Correct 177 ms 34888 KB Output is correct
27 Correct 160 ms 32288 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 21988 KB Output is correct
2 Correct 36 ms 24528 KB Output is correct
3 Correct 42 ms 23368 KB Output is correct
4 Correct 39 ms 24136 KB Output is correct
5 Correct 32 ms 23376 KB Output is correct
6 Correct 63 ms 23160 KB Output is correct
7 Correct 27 ms 23012 KB Output is correct
8 Correct 264 ms 43952 KB Output is correct
9 Correct 246 ms 45116 KB Output is correct
10 Correct 23 ms 22764 KB Output is correct
11 Correct 194 ms 37704 KB Output is correct
12 Correct 208 ms 36280 KB Output is correct
13 Correct 401 ms 47288 KB Output is correct
14 Correct 25 ms 23020 KB Output is correct
15 Correct 349 ms 39844 KB Output is correct
16 Correct 191 ms 35144 KB Output is correct
17 Correct 164 ms 32072 KB Output is correct
18 Correct 156 ms 32584 KB Output is correct
19 Correct 361 ms 42172 KB Output is correct
20 Correct 346 ms 43348 KB Output is correct
21 Correct 274 ms 44072 KB Output is correct
22 Correct 243 ms 39844 KB Output is correct
23 Correct 174 ms 34672 KB Output is correct
24 Correct 183 ms 31560 KB Output is correct
25 Correct 261 ms 40904 KB Output is correct
26 Correct 177 ms 34888 KB Output is correct
27 Correct 160 ms 32288 KB Output is correct
28 Incorrect 24 ms 22924 KB Extra information in the output file
29 Halted 0 ms 0 KB -