oj.uz

Submission #304750

# Submission time Handle Problem Language Result Execution time Memory
304750 2020-09-21T20:24:01 Z computerbox Cheap flights (LMIO18_pigus_skrydziai) C++14
12 / 100
 3000 ms 80968 KB 
#include <bits/stdc++.h>
#define FLASH ios_base::sync_with_stdio(0);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";


using namespace std;


set<pair<ll,ll> >adj[200010];

ll par[200010];
ll rankk[200010];

void make_set(ll n)
{
  for(ll i=1;i<=n;i++){par[i]=i;rankk[i]=1;}
}

ll findd(ll v)
{
  while(par[v]!=v)
  {
	par[v]=par[par[v]];
	v=par[v];  
  }	
  return v;
}

void make_union(ll a,ll b)
{
 a=findd(a);
 b=findd(b);
 if(a!=b)
 {
	if(rankk[a]>rankk[b])swap(a,b);
	rankk[b]+=rankk[a];
	par[a]=par[b];  
 }	
}

struct edge
{
  ll x,y,z;	
};

vector<edge>massiv;

ll sorthus(edge a,edge b)
{
  return a.z>b.z;	
}

ll n,m;
int main(){
FLASH;
cin>>n>>m;
for(ll i=1;i<=m;i++)
{
  ll x,y,z;
  cin>>x>>y>>z;
  adj[x].insert(mp(y,z));
  adj[y].insert(mp(x,z));	
}


ll maxx=0;
ll summ=0;
for(ll i=1;i<=n;i++)
{
  summ=0;
  for(auto j:adj[i])summ+=j.second;
  maxx=max(maxx,summ);	
}

for(ll i=1;i<=n;i++)
{
  for(auto j:adj[i])
  {
	for(auto j1:adj[j.first])
	{
	  ll y=j1.first;
	  if(y==i)continue;
	  auto yy=j1.first;
	  auto ch=adj[yy].lower_bound(mp(i,0));
	  if(ch!=adj[yy].end() && (*ch).first==i)
	  {
		maxx=max(maxx,j.second+j1.second+(*ch).second);
	  }	
    }  
  }	
}


cout<<maxx<<endl;

return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 345 ms 12416 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 6 ms 9792 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 6 ms 9728 KB Output is correct
11 Correct 7 ms 9788 KB Output is correct
12 Correct 7 ms 9836 KB Output is correct
13 Correct 6 ms 9728 KB Output is correct
14 Correct 7 ms 9728 KB Output is correct
15 Correct 7 ms 9728 KB Output is correct
16 Correct 6 ms 9728 KB Output is correct
17 Correct 7 ms 9728 KB Output is correct
18 Correct 9 ms 9856 KB Output is correct
19 Correct 13 ms 9984 KB Output is correct
20 Correct 6 ms 9728 KB Output is correct
21 Correct 7 ms 9728 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 345 ms 12416 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 6 ms 9792 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 6 ms 9728 KB Output is correct
11 Correct 7 ms 9788 KB Output is correct
12 Correct 7 ms 9836 KB Output is correct
13 Correct 6 ms 9728 KB Output is correct
14 Correct 7 ms 9728 KB Output is correct
15 Correct 7 ms 9728 KB Output is correct
16 Correct 6 ms 9728 KB Output is correct
17 Correct 7 ms 9728 KB Output is correct
18 Correct 9 ms 9856 KB Output is correct
19 Correct 13 ms 9984 KB Output is correct
20 Correct 6 ms 9728 KB Output is correct
21 Correct 7 ms 9728 KB Output is correct
22 Execution timed out 3073 ms 80968 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -