Submission #345926

#	Time	Username	Problem	Language	Result	Execution time	Memory
345926		dolijan	Traffic (IOI10_traffic)	C++14	100 / 100	1457 ms	156268 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
const int mn=(1e6)+100;
vector<vector<int> > graf(mn);
int parent[mn];
int sbtr[mn];
int dp[mn];
bool bio[mn];
int dfs1(int node,int p[])
{
    bio[node]=true;
    for(int i=0;i<graf[node].size();i++)
    {
        if(!bio[graf[node][i]])
        {
            int sta=dfs1(graf[node][i],p);
            dp[node]+=(p[graf[node][i]]+sta);
        }
    }
    return dp[node];
}
void dfs2(int node,int p[])
{
    bio[node]=true;
    for(int i=0;i<graf[node].size();i++)
    {
        if(!bio[graf[node][i]])
        {
            sbtr[node]=max(sbtr[node],dp[graf[node][i]]+p[graf[node][i]]);
            dfs2(graf[node][i],p);
        }
    }
}
int LocateCentre(int n,int p[],int s[],int d[])
{
    for(int i=0;i<n-1;i++)
    {
        graf[s[i]].push_back(d[i]);
        graf[d[i]].push_back(s[i]);
    }
    dfs1(0,p);
    for(int i=0;i<n;i++) bio[i]=false;
    dfs2(0,p);
    //for(int i=0;i<n;i++) cout<<sbtr[i]<<" ";
    //cout<<endl;
    int suma=0;
    for(int i=0;i<n;i++) suma+=p[i];
    int mini=suma;
    int ind;
    for(int i=0;i<n;i++)
    {
        int dole=sbtr[i];
        int gore=suma-dp[i]-p[i];
        //cout<<i<<" "<<dole<<" "<<gore<<endl;
        if(mini>max(dole,gore))
        {
            mini=max(dole,gore);
            ind=i;
        }
    }
    return ind;
}
/*
int main()
{
    int n;
    cin>>n;
    int p[n],s[n],d[n];
    for(int i=0;i<n;i++) cin>>p[i];
    for(int i=0;i<n-1;i++)
    {
        cin>>s[i]>>d[i];
    }
    cout<<LocateCentre(n,p,s,d)<<endl;
}
*/

Compilation message (stderr)

traffic.cpp: In function 'int dfs1(int, int*)':
traffic.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<graf[node].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~
traffic.cpp: In function 'void dfs2(int, int*)':
traffic.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<graf[node].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:61:12: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     return ind;
      |            ^~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25