Submission #378366

#	Time	Username	Problem	Language	Result	Execution time	Memory
378366		Bidrift	Traffic (IOI10_traffic)	C++17	100 / 100	1185 ms	157780 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[1000005], nodes(1000005,0), people(1000005,0), children(1000005, 0);
int fans = 0;

void DFS(int parent, int avoid){
    for (auto x: adj[parent]){
        if (x == avoid) continue;
        DFS(x,parent);
        children[parent]+= children[x];
        people[parent] = max(people[parent],children[x]);
    }
    people[parent] = max(people[parent], fans-children[parent]-nodes[parent]);
    children[parent] += nodes[parent];
}

int LocateCentre(int n, int p[], int s[], int d[]){
    for (int i = 0; i < n; i++){
        fans += p[i];
        nodes[i] = p[i];
    }
    for (int i = 0; i < n-1; i++){
        adj[s[i]].pb(d[i]);
        adj[d[i]].pb(s[i]);
    }
    DFS(0,-1);
    int ans, mini = INT32_MAX;
    for (int i = 0; i < n; i++){
        if (people[i] < mini){
            ans = i;
            mini = people[i];
        }
    }
    return ans;
}

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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:71:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |     return ans;
      |            ^~~

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