Submission #569960

#	Time	Username	Problem	Language	Result	Execution time	Memory
569960		Bidrift	Traffic (IOI10_traffic)	C++17	50 / 100	1374 ms	262144 KiB

traffic

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <string>
#include <fstream>
#include <list>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <iomanip>
#include <traffic.h>

#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define srt(a) sort(all(a));
#define srtc(a,comp) sort(all(a),comp);
#define srtb(a) sort(a.rbegin(),a.rend());
#define boost ios::sync_with_stdio(false); cin.tie(0); cin.tie(0);
using ll = long long;
using namespace std;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> ii;
typedef vector<ii> vpi;
const int dx[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //right left down up
void setIO(string name = "") { // name is nonempty for USACO file I/O
    ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output
    // alternatively, cin.tie(0)->sync_with_stdio(0);
    freopen((name+".in").c_str(), "r", stdin); // see Input & Output
    freopen((name+".out").c_str(), "w", stdout);
}

vi adj[1000100];
map<ii,int> weights;
vi popu;
int ans = 1e9;
int k;

int dfs1(int node, int parent){
    if (parent != node && adj[node].size() == 1){
        return popu[node];
    }
    int w = 0;
    for (auto x: adj[node]){
        if (x != parent){
            weights[{node,x}] = dfs1(x,node);
            //cout << node << " " << x << " " << weights[{node,x}] << endl;
            w += weights[{node,x}];
        }
    }
    w+=popu[node];
    //cout << node << " " << w << endl;
    //cout << endl;
    return w;
}

void dfs2(int node, int parent){
    int curr = 0;
    for (auto x: adj[node]){
        if (x != parent) curr = max(curr,weights[{node,x}]);
    }
    if (node == parent){
        //cout << node << " " << curr << endl;
        if (curr < ans){

            ans = curr;
            k = node;
        }
        for (auto x: adj[node]){
            if (x != parent) dfs2(x,node);
        }
        return;
    }
    int newweight = popu[parent];
    for (auto x: adj[parent]){
        if (x != node){
            newweight+=weights[{parent,x}];
        }
    }
    curr = max(curr,newweight);
    weights[{node,parent}] = newweight;
    if (curr < ans){
        ans = curr;
        k = node;
    }
    for (auto x: adj[node]){
        if (x != parent) dfs2(x,node);
    }
}

int LocateCentre(int N, int P[], int S[], int D[]){
    for (int i = 0; i < N-1; i++){
        adj[S[i]].pb(D[i]);
        adj[D[i]].pb(S[i]);
        popu.pb(P[i]);
    }
    popu.pb(P[N-1]);
    dfs1(0,0);
    dfs2(0,0);
    ans = 1e9;
   // cout << k << " " << ans << endl;
    return k;
}

Compilation message (stderr)

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

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