oj.uz

Submission #775593

# Submission time Handle Problem Language Result Execution time Memory
775593 2023-07-06T14:46:48 Z DobromirAngelov Traffic (IOI10_traffic) C++14
0 / 100
 11 ms 23800 KB 
#include<bits/stdc++.h>
#include "traffic.h"

using namespace std;

const int MAXN=1e6+5;
const int INF=2e9+5;

int a[MAXN];
vector<int> adj[MAXN];
int subtr[MAXN];

int dfs(int v,int par)
{
    subtr[v]=a[v];
    for(int i=0;i<adj[v].size();i++)
    {
        if(adj[v][i]==par) continue;
        subtr[v]+=dfs(adj[v][i], v);
    }
    return subtr[v];
}

int LocateCentre(int n,int w[],int u[],int v[])
{
    for(int i=0;i<n;i++)
    {
        a[i]=w[i];
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    dfs(0,-1);

    int ans=-1, best=INF;
    for(int i=0;i<n;i++)
    {
        int curMax=subtr[0]-subtr[i];
        for(int j=0;j<adj[i].size();j++)
        {
            curMax=max(curMax, subtr[adj[i][j]]);
        }
        if(curMax<best)
        {
            best=curMax;
            ans=i;
        }
    }

    return ans;
}

Compilation message

traffic.cpp: In function 'int dfs(int, int)':
traffic.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j=0;j<adj[i].size();j++)
      |                     ~^~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -