Submission #536306

#	Time	Username	Problem	Language	Result	Execution time	Memory
536306		Deepesson	Synchronization (JOI13_synchronization)	C++17	40 / 100	8071 ms	23356 KiB

synchronization

#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].size())return -1;
    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::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 (stderr)

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:39:39: warning: unused variable 'fecha' [-Wunused-variable]
   39 |         int abre = window[x][m].first,fecha=window[x][m].second;
      |                                       ^~~~~
synchronization.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
   47 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40