Termof's blog

By Termof, history, 18 months ago, In English

why i got TLE


i was upsolve the question at atcoder. question is about undirected graph E Art Gallery on Graph i submit the code 7 to 8 times but i got TLE. my code is same as others,

participant code (who got accepted)

my code (this is only solve function)

code start here

void solve() {

ll n,e,k;
cin>>n>>e>>k;

vector<vector<int>>ed(n);

for (int i = 0; i < e; ++i)
{
    ll a,b;
    cin>>a>>b;
    ed[a-1].push_back(b-1);
    ed[b-1].push_back(a-1);
}

vector<int> s(n,-1);
priority_queue<pair<int,int>>q;

for (int i = 0; i < k; ++i){
    ll a,b;
    cin>>a>>b;
    q.push({a-1,b});
    s[a-1]=b;
}

while(!q.empty()){
    auto [l,v] = q.top(); 
    q.pop();
        if(s[l]>v)
            continue;

        for(auto f : ed[l]){
            if(ckmax(s[f],v-1)){             
                q.push({f,s[f]});
            }
        }  
}

vector<int> ans;

for(int i=0;i<n;i++){
    if(s[i]>=0)
        ans.push_back(i+1);
}
cout<<ans.size()<<en;

print(ans);

}

code end

please anyone explain me, help was appreciated

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it