oj.uz

Submission #340666

# Submission time Handle Problem Language Result Execution time Memory
340666 2020-12-28T05:50:57 Z exopeng Traffic (IOI10_traffic) C++14
0 / 100
 17 ms 23916 KB 
#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++){
		if(adj[v][i]!=pa){
			dfs1(adj[v][i],v);
		}
		mn=max(mn,ct[adj[v][i]]+p[adj[v][i]]);
	}
	if(mn<ans){
		ans=mn;
		an=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=INF;
    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

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: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:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<adj[0].size();i++){
      |                 ~^~~~~~~~~~~~~~
traffic.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0;i<adj[0].size();i++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 15 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 15 ms 23788 KB Output is correct
6 Correct 15 ms 23788 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 16 ms 23788 KB Output is correct
10 Correct 15 ms 23788 KB Output is correct
11 Correct 15 ms 23788 KB Output is correct
12 Correct 15 ms 23788 KB Output is correct
13 Correct 16 ms 23808 KB Output is correct
14 Correct 15 ms 23788 KB Output is correct
15 Correct 15 ms 23788 KB Output is correct
16 Correct 15 ms 23788 KB Output is correct
17 Correct 17 ms 23788 KB Output is correct
18 Correct 16 ms 23788 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Correct 15 ms 23788 KB Output is correct
21 Correct 16 ms 23788 KB Output is correct
22 Correct 16 ms 23916 KB Output is correct
23 Incorrect 16 ms 23916 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 15 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 15 ms 23788 KB Output is correct
6 Correct 15 ms 23788 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 16 ms 23788 KB Output is correct
10 Correct 15 ms 23788 KB Output is correct
11 Correct 15 ms 23788 KB Output is correct
12 Correct 15 ms 23788 KB Output is correct
13 Correct 16 ms 23808 KB Output is correct
14 Correct 15 ms 23788 KB Output is correct
15 Correct 15 ms 23788 KB Output is correct
16 Correct 15 ms 23788 KB Output is correct
17 Correct 17 ms 23788 KB Output is correct
18 Correct 16 ms 23788 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Correct 15 ms 23788 KB Output is correct
21 Correct 16 ms 23788 KB Output is correct
22 Correct 16 ms 23916 KB Output is correct
23 Incorrect 16 ms 23916 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 15 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 15 ms 23788 KB Output is correct
6 Correct 15 ms 23788 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 16 ms 23788 KB Output is correct
10 Correct 15 ms 23788 KB Output is correct
11 Correct 15 ms 23788 KB Output is correct
12 Correct 15 ms 23788 KB Output is correct
13 Correct 16 ms 23808 KB Output is correct
14 Correct 15 ms 23788 KB Output is correct
15 Correct 15 ms 23788 KB Output is correct
16 Correct 15 ms 23788 KB Output is correct
17 Correct 17 ms 23788 KB Output is correct
18 Correct 16 ms 23788 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Correct 15 ms 23788 KB Output is correct
21 Correct 16 ms 23788 KB Output is correct
22 Correct 16 ms 23916 KB Output is correct
23 Incorrect 16 ms 23916 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 15 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 15 ms 23788 KB Output is correct
6 Correct 15 ms 23788 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 16 ms 23788 KB Output is correct
10 Correct 15 ms 23788 KB Output is correct
11 Correct 15 ms 23788 KB Output is correct
12 Correct 15 ms 23788 KB Output is correct
13 Correct 16 ms 23808 KB Output is correct
14 Correct 15 ms 23788 KB Output is correct
15 Correct 15 ms 23788 KB Output is correct
16 Correct 15 ms 23788 KB Output is correct
17 Correct 17 ms 23788 KB Output is correct
18 Correct 16 ms 23788 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Correct 15 ms 23788 KB Output is correct
21 Correct 16 ms 23788 KB Output is correct
22 Correct 16 ms 23916 KB Output is correct
23 Incorrect 16 ms 23916 KB Output isn't correct
24 Halted 0 ms 0 KB -