oj.uz

Submission #536304

# Submission time Handle Problem Language Result Execution time Memory
536304 2022-03-12T18:46:55 Z Deepesson Synchronization (JOI13_synchronization) C++17
0 / 100
 67 ms 42068 KB 
#include <bits/stdc++.h>
#define MAX 205000
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
int N,M,Q;
std::vector<pii> window[MAX];
bool estado[MAX];
int val[MAX];
void atualiza(int x,int t){
    if(estado[x]){///Aberta
        window[x].push_back({val[x],t});
        estado[x]=false;
    }else {
        estado[x]=true;
        val[x]=t;
    }
}
int proximo(int x,int t){
    if(window[x].back().second<t)return -1;
    int l=0,r=window[x].size()-1;
    while(l<r){
        int m = (l+r)/2;
        int abre = window[x][m].first,fecha=window[x][m].second;
        if(abre>=t){
            r=m;
        }else l=m+1;
    }
    ///Dentro da janela
    if(window[x][l].second>=t)return t;
    ///Esperar ateh a proxima janela
    return window[x][l+1].first;
}
int proximoinv(int x,int t){
    if(window[x].front().first>t)return -1;
    int l=0,r=window[x].size()-1;
    while(l<r){
        int m = (l+r+1)/2;
        int abre = window[x][m].first,fecha=window[x][m].second;
        if(abre<=t){
            l=m;
        }else r=m-1;
    }
    ///Dentro da janela
    if(window[x][l].second>=t)return t;
    if(window[x][l].second<=t)return window[x][l].second;
}
int resps[MAX];
bool existe[MAX];
int dfs(int pos,int prev){
    int size=1;
    for(auto&x:con[pos]){
        if(x.first==prev)continue;
        if(!existe[x.first])continue;
        int b=dfs(x.first,pos);
        size+=b;
    }
    return size;
}
int centro=0;
int find_centroide(int pos,int prev,int sz){
    int max=0;
    int size=1;
    for(auto&x:con[pos]){
        if(x.first==prev)continue;
        if(existe[x.first])continue;
        int b=dfs(x.first,pos);
        size+=b;
        max=std::max(max,b);
    }
    max=std::max(max,sz-size);
    if(max<=sz/2)centro=pos;
    return size;
}
int count=0;
void search(int pos,int prev,int time){
   /// std::cout<<pos<<" "<<prev<<" "<<time<<"\n";
    if(time==-1)return;
    ++count;
    for(auto&x:con[pos]){
       /// if(existe[x.first])continue;
        if(prev==x.first)continue;
        search(x.first,pos,proximoinv(x.second,time));
    }
}
void centroide(int x){
    int sz = dfs(x,-1);
    find_centroide(x,-1,sz);
    int C = centro;
    existe[C]=true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>M>>Q;
    for(int i=0;i!=N-1;++i){
        int a,b;
        std::cin>>a>>b;
        --a;--b;
        con[a].push_back({b,i});
        con[b].push_back({a,i});
    }
    for(int i=0;i!=M;++i){
        int x;
        std::cin>>x;
            --x;
        atualiza(x,i);
    }
    for(int i=0;i!=N;++i){
        if(estado[i])atualiza(i,M+1);
       /// for(auto&x:window[i])std::cout<<"Window "<<x.first<<" "<<x.second<<" "<<i<<"\n";
    }
    ///centroide(0);
    for(int i=0;i!=Q;++i){
        int x;std::cin>>x;--x;
        count=0;search(x,-1,M+1);
        std::cout<<count<<"\n";
    }
}

Compilation message

synchronization.cpp: In function 'int proximo(int, int)':
synchronization.cpp:23:39: warning: unused variable 'fecha' [-Wunused-variable]
   23 |         int abre = window[x][m].first,fecha=window[x][m].second;
      |                                       ^~~~~
synchronization.cpp: In function 'int proximoinv(int, int)':
synchronization.cpp:38:39: warning: unused variable 'fecha' [-Wunused-variable]
   38 |         int abre = window[x][m].first,fecha=window[x][m].second;
      |                                       ^~~~~
synchronization.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9892 KB Output is correct
2 Runtime error 12 ms 19944 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 42068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9964 KB Output is correct
2 Runtime error 13 ms 19920 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 35576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Runtime error 13 ms 19964 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -