Submission #340657

#	Time	Username	Problem	Language	Result	Execution time	Memory
340657		exopeng	Traffic (IOI10_traffic)	C++14	75 / 100	5038 ms	231448 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 = 2e9+10;
const long long MOD = 1e9+7;
const int MAXN = 1e6+10;
//store test cases here
/*


*/
int n;
int p[MAXN];
multiset<int,greater<int> > ms;
int ans=INF;
int an=0;
vector<int> adj[MAXN];
int ct[MAXN];
int 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]));
	int t2=ct[v]+p[v];
	ct[pa]-=ct[v]+p[v];
	ct[v]+=p[pa]+ct[pa];
	ms.is(ct[pa]+p[pa]);
	int t1=ct[pa]+p[pa];
	if((int)*ms.begin()<ans){
		ans=*ms.begin();
		an=v;
	}
	for(int i=0;i<adj[v].size();i++){
		if(adj[v][i]!=pa){
			dfs1(adj[v][i],v);
		}
	}
	ms.erase(ms.find(t1));
	ct[pa]=temp;
	ct[v]=temp1;
	ms.is(t2);
}
long long LocateCentre(int ns, int ps[], int ss[],int ds[]) {
	ans=INF;
	n=ns;
	for(int i=0;i<n;i++){
		p[i]=ps[i];
	}
	//handle n=1 
	if(n==1){
		return 0;
	}
	for(int i=0;i<n-1;i++){
    	adj[ss[i]].pb(ds[i]);
    	adj[ds[i]].pb(ss[i]);
    }
    for(int i=0;i<adj[0].size();i++){
    	ct[0]+=dfs(adj[0][i],0);
    }
    ans=(int)*ms.begin();
    for(int i=0;i<adj[0].size();i++){
    	dfs1(adj[0][i],0);
    }
    return an;
}

Compilation message (stderr)

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

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