Submission #337582

#	Time	Username	Problem	Language	Result	Execution time	Memory
337582		exopeng	Traffic (IOI10_traffic)	C++14	0 / 100	17 ms	23916 KiB

traffic

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;

#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define pii pair<int,int>
#define pdd pair<double,double>
#define is insert
const long long INF = 1e16;
const long long MOD = 1e9+7;
const int MAXN = 1e6+10;
//store test cases here
/*


*/
int n;
int p[MAXN];
int s[MAXN];
int d[MAXN];
multiset<int,greater<int> > ms;
long long ans=INF;
vector<int> adj[MAXN];
long long ct[MAXN];
long long dfs(int v,int pa){
	for(int i=0;i<adj[v].size();i++){
		if(adj[v][i]!=pa){
			ct[v]+=dfs(adj[v][i],v);
		}
	}
	ms.is(ct[v]+p[v]);
	return ct[v]+p[v];
}
void dfs1(int v,int pa){
	long long temp=ct[pa];
	long long temp1=ct[v];
	ms.erase(ms.find(ct[v]+p[v]));
	ct[pa]-=ct[v]+p[v];
	ct[v]+=p[pa]+ct[pa];
	ms.is(ct[pa]+p[pa]);
	ans=min(ans,(long long)*ms.begin());
	for(int i=0;i<adj[v].size();i++){
		if(adj[v][i]!=pa){
			dfs1(adj[v][i],v);
		}
	}
	ms.erase(ms.find(ct[pa]+p[pa]));
	ct[pa]=temp;
	ct[v]=temp1;
	ms.is(ct[v]+p[v]);
}
long long LocateCentre(int ns, int ps[], int ss[],int ds[]) {
	n=ns;
	for(int i=0;i<n;i++){
		p[i]=ps[i];
	}
	for(int i=0;i<n-1;i++){
		s[i]=ss[i];
		d[i]=ds[i];
	}
	for(int i=0;i<n-1;i++){
    	adj[s[i]].pb(d[i]);
    	adj[d[i]].pb(s[i]);
    }
    for(int i=0;i<adj[0].size();i++){
    	ct[0]+=dfs(adj[0][i],0);
    }
    for(int i=0;i<n;i++){
    	//cout<<ct[i]<<"\n";
    }
    for(int i=0;i<adj[0].size();i++){
    	dfs1(adj[0][i],0);
    }
    return ans;
}

Compilation message (stderr)

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

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