Submission #168711

#	Time	Username	Problem	Language	Result	Execution time	Memory
168711		beso123	Evacuation plan (IZhO18_plan)	C++14	0 / 100	1233 ms	59492 KiB

plan

#include <bits/stdc++.h>
#define int long long
#define INT_MAX LONG_LONG_MAX
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,m,N,q,lg=17,timer=1,ans[100005];
map<pair<int,int>,int> mp;
vector<int> g[100005],d,used,p,Size,g1[100005],dp[20],tin,tout;
multiset<pair<int,int> > s;
vector<pii> Q,ed;
void MS(){
    for(int k=1;k<=n;k++){
        p[k]=k;
        Size[k]=d[k];
    }
}
int FS(int v){
    if(p[v]==v) return v;
    return p[v]=FS(p[v]);
}
void US(int a,int b){
    a=FS(a);
    b=FS(b);
    if(a!=b){
               g1[a].push_back(b);
    g1[b].push_back(a);
        p[b]=a;
        Size[a]=min(Size[a],Size[b]);
    }
}
void DFS(int v,int p){
    used[v]=1;
    dp[v][0]=p;
    for(int k=1;k<dp[v].size();k++)
        dp[v][k]=dp[dp[v][k-1]][k-1];
        tin[v]=timer++;
    for(int k=0;k<g1[v].size();k++){
        int to=g1[v][k];
        if(used[to]==0)
            DFS(to,v);
    }
    tout[v]=timer++;
}
bool tree(int a,int b){
    if(tin[a]<=tin[b] && tout[a]>=tout[b])
        return true;
     return false;
}
int LCA(int a,int b){
    if(tree(a,b)) return a;
    if(tree(b,a)) return b;
    int t=a;
    for(int k=N;k>=0;k--){
        if(dp[t][k]!=0){
        int to=dp[t][k];
        if(!tree(to,b))
            t=to;
    }
}
    return dp[t][0];
}
main(){
cin>>n>>m;
for(int k=1;k<=m;k++){
    int a,b,c;
    cin>>a>>b>>c;
    mp[{a,b}]=c;
    mp[{b,a}]=c;
    g[a].push_back(b);
    g[b].push_back(a);
}
cin>>N;
d.resize(n+1,INT_MAX);
used.resize(n+1,0);
for(int k=1;k<=N;k++){
    int qal;
    cin>>qal;
    d[qal]=0;
    s.insert({0,qal});
}
while(!s.empty()){
   int v=s.begin()->second;
   used[v]=1;
   s.erase(s.begin());
   for(int k=0;k<g[v].size();k++){
    int to=g[v][k];
    if(used[to]==0 && d[to]>d[v]+mp[{v,to}]){
        d[to]=d[v]+mp[{to,v}];
        s.insert({d[to],to});
    }
   }
}
for(int k=1;k<=n;k++){
    ed.push_back({d[k],k});
}
sort(ed.begin(),ed.end());
reverse(ed.begin(),ed.end());
cin>>q;
for(int k=1;k<=q;k++){
int a,b;
cin>>a>>b;
Q.push_back({a,b});
}
Size.resize(n+1,0);
p.resize(n+1,0);
used.resize(0);
used.resize(n+1,0);
MS();
for(int k=0;k<ed.size();k++){
    int v=ed[k].y;
    used[v]=1;
    for(int k=0;k<g[v].size();k++)
        if(used[g[v][k]])
        US(v,g[v][k]);
}
used.resize(0);
used.resize(n+1,0);
tin.resize(n+1,0);
tout.resize(n+1,0);
for(int k=0;k<=lg;k++)
    dp[k].resize(n+1,0);
DFS(ed[ed.size()-1].y,0);
for(int k=0;k<Q.size();k++){
    int a=Q[k].x,b=Q[k].y;
    int lc=LCA(a,b);
   cout<<d[lc]<<endl;
}
return 0;
}

Compilation message (stderr)

plan.cpp:3:0: warning: "INT_MAX" redefined
 #define INT_MAX LONG_LONG_MAX
 
In file included from /usr/include/c++/7/climits:42:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:39,
                 from plan.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/7/include-fixed/limits.h:120:0: note: this is the location of the previous definition
 #define INT_MAX __INT_MAX__
 
plan.cpp: In function 'void DFS(long long int, long long int)':
plan.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=1;k<dp[v].size();k++)
                 ~^~~~~~~~~~~~~
plan.cpp:36:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int k=1;k<dp[v].size();k++)
     ^~~
plan.cpp:38:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         tin[v]=timer++;
         ^~~
plan.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<g1[v].size();k++){
                 ~^~~~~~~~~~~~~
plan.cpp: At global scope:
plan.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
plan.cpp: In function 'int main()':
plan.cpp:87:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<g[v].size();k++){
                ~^~~~~~~~~~~~
plan.cpp:111:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int k=0;k<ed.size();k++){
             ~^~~~~~~~~~
plan.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<g[v].size();k++)
                 ~^~~~~~~~~~~~
plan.cpp:125:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int k=0;k<Q.size();k++){
             ~^~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46