oj.uz

답안 #1114950

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114950 2024-11-19T20:26:51 Z HoriaHaivas Inside information (BOI21_servers) C++14
50 / 100
 469 ms 47288 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,0,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

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 21996 KB Output is correct
2 Correct 36 ms 23120 KB Output is correct
3 Correct 42 ms 22088 KB Output is correct
4 Correct 34 ms 23152 KB Output is correct
5 Correct 38 ms 23404 KB Output is correct
6 Correct 72 ms 23240 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 21996 KB Output is correct
2 Correct 36 ms 23120 KB Output is correct
3 Correct 42 ms 22088 KB Output is correct
4 Correct 34 ms 23152 KB Output is correct
5 Correct 38 ms 23404 KB Output is correct
6 Correct 72 ms 23240 KB Output is correct
7 Incorrect 30 ms 21892 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 21988 KB Output is correct
2 Correct 268 ms 41828 KB Output is correct
3 Correct 320 ms 41688 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 21988 KB Output is correct
2 Correct 268 ms 41828 KB Output is correct
3 Correct 320 ms 41688 KB Output is correct
4 Incorrect 38 ms 22048 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 22060 KB Output is correct
2 Correct 206 ms 34572 KB Output is correct
3 Correct 219 ms 34332 KB Output is correct
4 Correct 447 ms 47288 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 22060 KB Output is correct
2 Correct 206 ms 34572 KB Output is correct
3 Correct 219 ms 34332 KB Output is correct
4 Correct 447 ms 47288 KB Output is correct
5 Incorrect 26 ms 20600 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 20716 KB Output is correct
2 Correct 378 ms 36284 KB Output is correct
3 Correct 195 ms 31816 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 20716 KB Output is correct
2 Correct 378 ms 36284 KB Output is correct
3 Correct 195 ms 31816 KB Output is correct
4 Incorrect 29 ms 20784 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 20716 KB Output is correct
2 Correct 233 ms 34408 KB Output is correct
3 Correct 268 ms 34348 KB Output is correct
4 Correct 419 ms 47288 KB Output is correct
5 Correct 22 ms 21996 KB Output is correct
6 Correct 405 ms 36668 KB Output is correct
7 Correct 225 ms 31816 KB Output is correct
8 Correct 189 ms 32072 KB Output is correct
9 Correct 222 ms 32352 KB Output is correct
10 Correct 406 ms 40100 KB Output is correct
11 Correct 443 ms 40024 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 20716 KB Output is correct
2 Correct 233 ms 34408 KB Output is correct
3 Correct 268 ms 34348 KB Output is correct
4 Correct 419 ms 47288 KB Output is correct
5 Correct 22 ms 21996 KB Output is correct
6 Correct 405 ms 36668 KB Output is correct
7 Correct 225 ms 31816 KB Output is correct
8 Correct 189 ms 32072 KB Output is correct
9 Correct 222 ms 32352 KB Output is correct
10 Correct 406 ms 40100 KB Output is correct
11 Correct 443 ms 40024 KB Output is correct
12 Incorrect 21 ms 22064 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 21996 KB Output is correct
2 Correct 56 ms 23116 KB Output is correct
3 Correct 47 ms 20924 KB Output is correct
4 Correct 36 ms 23216 KB Output is correct
5 Correct 33 ms 23304 KB Output is correct
6 Correct 67 ms 23172 KB Output is correct
7 Correct 28 ms 22136 KB Output is correct
8 Correct 302 ms 41644 KB Output is correct
9 Correct 312 ms 41584 KB Output is correct
10 Correct 25 ms 22112 KB Output is correct
11 Correct 227 ms 34392 KB Output is correct
12 Correct 227 ms 34408 KB Output is correct
13 Correct 426 ms 47256 KB Output is correct
14 Correct 31 ms 20692 KB Output is correct
15 Correct 368 ms 36376 KB Output is correct
16 Correct 205 ms 31816 KB Output is correct
17 Correct 197 ms 32016 KB Output is correct
18 Correct 203 ms 32584 KB Output is correct
19 Correct 402 ms 40132 KB Output is correct
20 Correct 469 ms 40128 KB Output is correct
21 Correct 326 ms 40744 KB Output is correct
22 Correct 273 ms 36512 KB Output is correct
23 Correct 249 ms 31560 KB Output is correct
24 Correct 221 ms 31560 KB Output is correct
25 Correct 257 ms 38072 KB Output is correct
26 Correct 179 ms 31432 KB Output is correct
27 Correct 157 ms 32328 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 21996 KB Output is correct
2 Correct 56 ms 23116 KB Output is correct
3 Correct 47 ms 20924 KB Output is correct
4 Correct 36 ms 23216 KB Output is correct
5 Correct 33 ms 23304 KB Output is correct
6 Correct 67 ms 23172 KB Output is correct
7 Correct 28 ms 22136 KB Output is correct
8 Correct 302 ms 41644 KB Output is correct
9 Correct 312 ms 41584 KB Output is correct
10 Correct 25 ms 22112 KB Output is correct
11 Correct 227 ms 34392 KB Output is correct
12 Correct 227 ms 34408 KB Output is correct
13 Correct 426 ms 47256 KB Output is correct
14 Correct 31 ms 20692 KB Output is correct
15 Correct 368 ms 36376 KB Output is correct
16 Correct 205 ms 31816 KB Output is correct
17 Correct 197 ms 32016 KB Output is correct
18 Correct 203 ms 32584 KB Output is correct
19 Correct 402 ms 40132 KB Output is correct
20 Correct 469 ms 40128 KB Output is correct
21 Correct 326 ms 40744 KB Output is correct
22 Correct 273 ms 36512 KB Output is correct
23 Correct 249 ms 31560 KB Output is correct
24 Correct 221 ms 31560 KB Output is correct
25 Correct 257 ms 38072 KB Output is correct
26 Correct 179 ms 31432 KB Output is correct
27 Correct 157 ms 32328 KB Output is correct
28 Incorrect 31 ms 21900 KB Extra information in the output file
29 Halted 0 ms 0 KB -