oj.uz

Submission #489326

# Submission time Handle Problem Language Result Execution time Memory
489326 2021-11-22T12:44:52 Z cpp219 Inside information (BOI21_servers) C++14
5 / 100
 168 ms 23684 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 29 ms 17228 KB Output is correct
2 Correct 39 ms 17524 KB Output is correct
3 Correct 37 ms 17420 KB Output is correct
4 Correct 49 ms 17584 KB Output is correct
5 Correct 41 ms 17456 KB Output is correct
6 Correct 40 ms 17280 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17228 KB Output is correct
2 Correct 39 ms 17524 KB Output is correct
3 Correct 37 ms 17420 KB Output is correct
4 Correct 49 ms 17584 KB Output is correct
5 Correct 41 ms 17456 KB Output is correct
6 Correct 40 ms 17280 KB Output is correct
7 Correct 29 ms 17228 KB Output is correct
8 Correct 42 ms 17092 KB Output is correct
9 Correct 39 ms 17092 KB Output is correct
10 Correct 53 ms 17224 KB Output is correct
11 Correct 58 ms 17008 KB Output is correct
12 Correct 39 ms 16828 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17332 KB Output is correct
2 Incorrect 131 ms 23076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17332 KB Output is correct
2 Incorrect 131 ms 23076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17272 KB Output is correct
2 Incorrect 138 ms 21368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17272 KB Output is correct
2 Incorrect 138 ms 21368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17280 KB Output is correct
2 Incorrect 168 ms 23684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17280 KB Output is correct
2 Incorrect 168 ms 23684 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 17288 KB Output is correct
2 Incorrect 121 ms 21388 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 17288 KB Output is correct
2 Incorrect 121 ms 21388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17268 KB Output is correct
2 Correct 37 ms 17532 KB Output is correct
3 Correct 49 ms 17352 KB Output is correct
4 Correct 42 ms 17664 KB Output is correct
5 Correct 40 ms 17476 KB Output is correct
6 Correct 39 ms 17320 KB Output is correct
7 Correct 29 ms 17324 KB Output is correct
8 Incorrect 132 ms 23088 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17268 KB Output is correct
2 Correct 37 ms 17532 KB Output is correct
3 Correct 49 ms 17352 KB Output is correct
4 Correct 42 ms 17664 KB Output is correct
5 Correct 40 ms 17476 KB Output is correct
6 Correct 39 ms 17320 KB Output is correct
7 Correct 29 ms 17324 KB Output is correct
8 Incorrect 132 ms 23088 KB Output isn't correct
9 Halted 0 ms 0 KB -