oj.uz

Submission #536306

# Submission time Handle Problem Language Result Execution time Memory
536306 2022-03-12T18:48:04 Z Deepesson Synchronization (JOI13_synchronization) C++17
40 / 100
 8000 ms 23356 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].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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9936 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 7 ms 9956 KB Output is correct
7 Correct 17 ms 10848 KB Output is correct
8 Correct 19 ms 10700 KB Output is correct
9 Correct 17 ms 10716 KB Output is correct
10 Correct 158 ms 19152 KB Output is correct
11 Correct 144 ms 19192 KB Output is correct
12 Correct 132 ms 18640 KB Output is correct
13 Correct 119 ms 18992 KB Output is correct
14 Correct 139 ms 18936 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 19784 KB Output is correct
2 Correct 136 ms 20724 KB Output is correct
3 Correct 104 ms 22692 KB Output is correct
4 Correct 104 ms 21976 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 6 ms 9944 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 8 ms 9944 KB Output is correct
6 Correct 9 ms 9956 KB Output is correct
7 Correct 36 ms 10828 KB Output is correct
8 Correct 349 ms 19420 KB Output is correct
9 Correct 304 ms 19448 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 16780 KB Output is correct
2 Execution timed out 8032 ms 23356 KB Time limit exceeded
3 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 Correct 5 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 9 ms 9940 KB Output is correct
6 Correct 96 ms 10888 KB Output is correct
7 Correct 3349 ms 20156 KB Output is correct
8 Correct 305 ms 19404 KB Output is correct
9 Execution timed out 8071 ms 19440 KB Time limit exceeded
10 Halted 0 ms 0 KB -