제출 #619407

#제출 시각아이디문제언어결과실행 시간메모리
619407Icebear16Traffic (IOI10_traffic)C++14
50 / 100
82 ms35844 KiB
#include "traffic.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define INF 1e18//change to const int INF=1e18 if causing problem const ll MOD=998244353; const ll alt=1e10; const ll inf=1e9+7;//Precalc is not a bad idea //#define int ll #define pb push_back #define pf push_front #define mp make_pair #define fi first #define se second #define mod(a) (a+inf)%inf #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define sz(a) a.size() vector<set<int> > adj(100000); priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; vector<int> vis(100000,0); vector<bool> visd(100000,false); int LocateCentre(int N, int pp[], int s[], int d[]){ for(int i=0;i<N-1;i++){ adj[s[i]].insert(d[i]); adj[d[i]].insert(s[i]); } for(int i=0;i<N;i++){ if(adj[i].size()<=1){ q.push(mp(pp[i],i)); visd[i]=true; } } while(sz(q)>1){ int a=q.top().fi,b=q.top().se; q.pop(); auto y=*adj[b].begin(); pp[y]+=a; adj[y].erase(b); if(sz(adj[y])==1){ q.push(mp(pp[y],y)); visd[y]=true; } } return q.top().se; } //Icebear16
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...