Submission #340672

#	Time	Username	Problem	Language	Result	Execution time	Memory
340672		exopeng	Traffic (IOI10_traffic)	C++14	100 / 100	1421 ms	168428 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 s[MAXN];
int d[MAXN];
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){
	int temp=ct[pa];
	int 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];
	int mn=0;
	for(int i=0;i<adj[v].size();i++){
		mn=max(mn,ct[adj[v][i]]+p[adj[v][i]]);
	}
	if(mn<ans){
		ans=mn;
		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);
}
int LocateCentre(int ns, int ps[], int ss[],int ds[]) {
	ans=INF;
	n=ns;
	copy(ps,ps+n,p);
	//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]);
    }
    int mn=0;
    for(int i=0;i<adj[0].size();i++){
    	int ms=dfs(adj[0][i],0);
    	ct[0]+=ms;
    	mn=max(mn,ms);
    }
    ans=mn;
    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:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0;i<adj[v].size();i++){
      |              ~^~~~~~~~~~~~~~
traffic.cpp: In function 'void dfs1(int, int)':
traffic.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=0;i<adj[v].size();i++){
      |              ~^~~~~~~~~~~~~~
traffic.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<adj[v].size();i++){
      |              ~^~~~~~~~~~~~~~
traffic.cpp:49:6: warning: unused variable 't2' [-Wunused-variable]
   49 |  int t2=ct[v]+p[v];
      |      ^~
traffic.cpp:53:6: warning: unused variable 't1' [-Wunused-variable]
   53 |  int t1=ct[pa]+p[pa];
      |      ^~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<adj[0].size();i++){
      |                 ~^~~~~~~~~~~~~~
traffic.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i<adj[0].size();i++){
      |                 ~^~~~~~~~~~~~~~

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