| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 337824 |
2020-12-21T18:43:16 Z |
exopeng |
Traffic (IOI10_traffic) |
C++14 |
|
15 ms |
23936 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];
int s[MAXN];
int d[MAXN];
multiset<int,greater<int> > ms;
int ans=INF;
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];
ans=min(ans,(int)*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(t1));
ct[pa]=temp;
ct[v]=temp1;
ms.is(t2);
}
long long LocateCentre(int ns, int ps[], int ss[],int ds[]) {
ms.clear();
ans=INF;
n=ns;
for(int i=0;i<n;i++){
adj[i].clear();
ct[i]=0;
}
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];
}
//handle n=1
if(n==1){
return 0;
}
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);
}
ans=min(ans,(int)*ms.begin());
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
traffic.cpp: In function '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:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<adj[v].size();i++){
| ~^~~~~~~~~~~~~~
traffic.cpp: In function 'long long int LocateCentre(int, int*, int*, int*)':
traffic.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i=0;i<adj[0].size();i++){
| ~^~~~~~~~~~~~~~
traffic.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i=0;i<adj[0].size();i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23936 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23936 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23936 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23936 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
