Submission #368548

#	Time	Username	Problem	Language	Result	Execution time	Memory
368548		1306439119	Traffic (IOI10_traffic)	C++11	100 / 100	1279 ms	174852 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pi pair<int, int>
#define endl '\n'

void setIO(string name = "") { 
    ios_base::sync_with_stdio(0); 
	cin.tie(0);     
    if (name.length()) {
        freopen((name+".in").c_str(), "r", stdin); 
        freopen((name+".out").c_str(), "w", stdout);
    }
}
int n, total;
vector<int> adj[1000000];
int val[1000000], children[1000000], ans[1000000];

void dfs(int curr, int prev){    
    
    for(int c : adj[curr]){
        if(prev != c){            
            dfs(c, curr);
            children[curr] += children[c];
            ans[curr] = max(ans[curr], children[c]);
        }
    }

    children[curr] += val[curr];    
    ans[curr] = max(ans[curr], total - children[curr]);        
}

int LocateCentre(int n, int* p, int* s, int* d){
    for(int i = 0; i < n; i++){        
        val[i] = p[i];
        total += p[i];
    }
    for(int i = 0; i < n-1; i++){        
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }        

    dfs(0, 0);

    int res = INT_MAX, ret = -1;
    for(int i = 0; i < n; i++){                
        if(ans[i] < res){            
            res = ans[i];
            ret = i;
        }
    }

    return ret;
}

/*int main(){			 
    setIO("");               
    int* p = new int[5]; 
    int* s = new int[4]; 
    int* d = new int[4];
    p[0] = 10, p[1] = 10, p[2] = 10, p[3] = 20, p[4] = 20;
    s[0] = 0, s[1] = 1, s[2] = 2, s[3] = 3;
    d[0] = 2, d[1] = 2, d[2] = 3, d[3] = 4;    
    cout << LocateCentre(5, p, s, d) << endl;;

    return 0;
}*/

Compilation message (stderr)

traffic.cpp: In function 'void setIO(std::string)':
traffic.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   12 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffic.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   13 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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