oj.uz

Submission #489324

# Submission time Handle Problem Language Result Execution time Memory
489324 2021-11-22T12:42:36 Z cpp219 Inside information (BOI21_servers) C++14
5 / 100
 235 ms 24264 KB 
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll inf = 1e9 + 7;

vector<ll> qcnt[N];
vector<LL> g[N],qif[N];;
ll n,Q,ans[N],ban[N],bit[N],child[N];

void upd(ll p,ll val){
    for (ll i = p;i < N;i += i & -i) bit[i] += val;
}
ll Get(ll p){
    ll res = 0;
    for (ll i = p;i > 0;i -= i & -i) res += bit[i];
    return res;
}

void dfs_sz(ll u,ll p){
    child[u] = 1;
    for (auto i : g[u]){
        ll v = i.sc;
        if (v == p || ban[v]) continue;
        dfs_sz(v,u); child[u] += child[v];
    }
}
ll Find_cent(ll u,ll p,ll sz){
    ll mx = 0;
    for (auto i : g[u])
        if (i.sc != p && !ban[i.sc] && child[mx] < child[i.sc]) mx = i.sc;
    if (max(child[mx],sz - child[u])*2 <= sz) return u;
    return Find_cent(mx,u,sz);
}

ll in_time[N];
void dfs_in(ll u,ll p,ll lastVal){
    in_time[u] = lastVal; upd(lastVal,1);
    for (auto i : g[u]) if (i.sc != p && !ban[i.sc]){
        if (i.fs >= lastVal) dfs_in(i.sc,u,i.fs);
    }
}
void dfs_out(ll u,ll p,ll lastVal){
    in_time[u] = inf; upd(lastVal,-1);
    for (auto i : g[u]) if (i.sc != p && !ban[i.sc]){
        if (i.fs >= lastVal) dfs_out(i.sc,u,i.fs);
    }
}

void Answer(ll now){
    for (auto i : qcnt[now]) ans[i] += Get(i);
    for (auto i : qif[now])
        if (in_time[i.sc] <= i.fs) ans[i.fs] = -1;
}
void dfs_solve(ll u,ll p,ll lastVal){
    Answer(u);
    for (auto i : g[u]) if (i.sc != p && !ban[i.sc]){
        if (i.fs < lastVal) dfs_solve(i.sc,u,i.fs);
    }
}

void solve(ll now,ll par){
    dfs_sz(now,0); ll cent = Find_cent(now,0,child[now]);
    sort(g[cent].begin(),g[cent].end());
    dfs_in(cent,0,1);
    Answer(cent);
    for (auto i : g[cent]) if (i.sc != par && !ban[i.sc]){
        dfs_out(i.sc,cent,i.fs);
        upd(in_time[cent],-1); in_time[cent] = i.fs;
        upd(in_time[cent],1);
        dfs_solve(i.sc,cent,i.fs);
    }
    ban[cent] = 1; upd(in_time[cent],-1); in_time[cent] = inf;

    for (auto i : g[cent])
        if (i.sc != par && !ban[i.sc]) solve(i.sc,cent);
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin>>n>>Q; Q += n - 1;
    for (ll i = 1;i <= Q;i++){
        char c; cin>>c; ll x,y;
        if (c == 'S'){
            ans[i] = -69;
            cin>>x>>y;
            g[x].push_back({i,y}); g[y].push_back({i,x});
        }
        else if (c == 'C'){
            cin>>x; ans[i] = 0;
            qcnt[x].push_back(i);
        }
        else{
            cin>>x>>y; ans[i] = -2;
            qif[y].push_back({i,x});
        }
    }
    //return 0;
    fill(in_time,in_time + n + 1,inf); //ban[2] = 1; solve(3,0);
    solve(1,0);

    for (ll i = 1;i <= Q;i++){
        if (ans[i] == -69) continue;
        if (ans[i] >= 0) cout<<ans[i]<<"\n";
        else{
            if (ans[i] == -2) cout<<"no";
            else cout<<"yes"; cout<<"\n";
        }
    }
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:117:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  117 |             else cout<<"yes"; cout<<"\n";
      |             ^~~~
servers.cpp:117:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  117 |             else cout<<"yes"; cout<<"\n";
      |                               ^~~~
servers.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17240 KB Output is correct
2 Correct 43 ms 18060 KB Output is correct
3 Correct 37 ms 17916 KB Output is correct
4 Correct 38 ms 18164 KB Output is correct
5 Correct 38 ms 17952 KB Output is correct
6 Correct 42 ms 17880 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17240 KB Output is correct
2 Correct 43 ms 18060 KB Output is correct
3 Correct 37 ms 17916 KB Output is correct
4 Correct 38 ms 18164 KB Output is correct
5 Correct 38 ms 17952 KB Output is correct
6 Correct 42 ms 17880 KB Output is correct
7 Correct 29 ms 17316 KB Output is correct
8 Correct 58 ms 17796 KB Output is correct
9 Correct 41 ms 17836 KB Output is correct
10 Correct 42 ms 17988 KB Output is correct
11 Correct 42 ms 17772 KB Output is correct
12 Correct 38 ms 17664 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17288 KB Output is correct
2 Incorrect 142 ms 23080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17288 KB Output is correct
2 Incorrect 142 ms 23080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17260 KB Output is correct
2 Incorrect 91 ms 21992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17260 KB Output is correct
2 Incorrect 91 ms 21992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17256 KB Output is correct
2 Incorrect 235 ms 24264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17256 KB Output is correct
2 Incorrect 235 ms 24264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17308 KB Output is correct
2 Incorrect 80 ms 22056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17308 KB Output is correct
2 Incorrect 80 ms 22056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17220 KB Output is correct
2 Correct 48 ms 18056 KB Output is correct
3 Correct 47 ms 17932 KB Output is correct
4 Correct 45 ms 18192 KB Output is correct
5 Correct 38 ms 17984 KB Output is correct
6 Correct 38 ms 17820 KB Output is correct
7 Correct 31 ms 17444 KB Output is correct
8 Incorrect 131 ms 23864 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17220 KB Output is correct
2 Correct 48 ms 18056 KB Output is correct
3 Correct 47 ms 17932 KB Output is correct
4 Correct 45 ms 18192 KB Output is correct
5 Correct 38 ms 17984 KB Output is correct
6 Correct 38 ms 17820 KB Output is correct
7 Correct 31 ms 17444 KB Output is correct
8 Incorrect 131 ms 23864 KB Output isn't correct
9 Halted 0 ms 0 KB -