Submission #1125995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125995		shiv_314	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2 ms	2624 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define endl "\n"
const ll mod = 1e9+7;
#define fi first
#define ss second
using ii = pair<ll,ll>;
#define pb push_back
#define mp make_pair
#define sz(x) (ll)(x).size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
#define vll vector<ll>
#define vvll vector<vll>
ll const N = 200100;
ll power(ll x,ll y,ll modd){ll res = 1;while(y){if(y&1) res = (res*x)%modd;y=y/2,x=(x*x)%modd;}return res%modd;}
// ll spf[N];
// void sieve()
// {
//    spf[1] = 1;
//    for (ll i=2; i<N; i++)
//        spf[i] = i;
//    for (ll i=4; i<N; i+=2)
//        spf[i] = 2;
//    for (ll i=3; i*i<N; i+=2)
//    {
//        if (spf[i]==i)
//        {
//            for (ll j=i*i; j<N; j+=i)
//                if (spf[j]==j)
//                    spf[j]=i;
//        }
//    }
// }
// map<ll,ll> getfactor(ll a)
// {
//    map<ll,ll> m;
//    while(a>1)
//    {
//        m[spf[a]]++;
//        a/=spf[a];
//    }
//    return m;
// }

//vll get_prime_factors(ll a){
//     ll num=a;
//     vll ans;
//     ans.pb(1);
//     for(ll i=2;(i*i)<=a;i++){
//         if(num%i==0){
//             ans.pb(i);
//             while(num%i==0){
//                 num/=i;
//             }
//         }
//     }
//     if(num>1)ans.pb(num);
//     return ans;
// }

#pragma region Debugger
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#pragma endregion Debugger
 
void print(int x) {cout << x;}
void print(long x) {cout << x;}
void print(long long x) {cout << x;}
void print(unsigned x) {cout << x;}
void print(unsigned long x) {cout << x;}
void print(unsigned long long x) {cout << x;}
void print(float x) {cout << x;}
void print(double x) {cout << x;}
void print(long double x) {cout << x;}
void print(char x) {cout << '\'' << x << '\'';}
void print(const char *x) {cout << '\"' << x << '\"';}
void print(const string &x) {cout << '\"' << x << '\"';}
void print(bool x) {cout << (x ? "true" : "false");}
 
template<typename T, typename V>
void print(const pair<T, V> &x) {print(x.first); cout << ','; print(x.second); cout << endl;}
template<typename T>
void print(const T &x) {int f = 0; for (auto &i: x) cout << (f++ ? "," : ""), print(i); cout << endl;}
void print_() {cout << "]\n";}
template <typename T, typename... V>
void print_(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; print_(v...) << endl;}


// ll parent[N],size_[N];
// void make(ll v)
// {
//     parent[v] = v;
//     size_[v] = 1;
// }
// ll find(ll v)
// {
//     if (v == parent[v])
//         return v;
//     return parent[v] = find(parent[v]);
// }
// void merge(ll a, ll b)
// {
//     a = find(a);
//     b = find(b);
//     if (a != b)
//     {
//         if(size_[a]<size_[b])
//             swap(a,b);
//         parent[b] = a;
//         size_[a] += size_[b];
//     }
// }
//ll fact[N];
//ll inv[N];
// void factorial(ll modd)
// {
//     ll i;
//     fact[0] = 1;
//     inv[0] = power(fact[0],modd-2,modd);
//     for(i=1;i<=N;i++)
//     {
//         fact[i] = (i*fact[i-1])%modd;
//         inv[i] = power(fact[i],modd-2,modd);
//     }
// }
// ll ncr(ll x,ll y,ll modd)
// {
//      if(x<y or x<0 or y<0)
//      return 0;
//		if(x==y or y==0)return 1;
//      ll temp = fact[x];
//      temp = (temp*inv[y])%modd;
//      temp = (temp*inv[x-y])%modd;
//      return temp;
// }
// ll loga[1000001];
// void precomp()
// {
//     loga[1] = 0;
//     for (ll i = 2; i <= 1000000; i++)
//         loga[i] = loga[i/2] + 1;
// }
// ll st[100001][20];
// void precomp1(ll n)
// {
//     for (ll i = 0; i < n; i++)
//         st[i][0] = a[i];
   
//     for (ll j = 1; j <= 19; j++)
//         for (ll i = 0; i + (1 << j) <= n; i++)
//             st[i][j] = min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
// }
// ll query1(ll L,ll R)
// {
//     ll j = loga[R - L + 1];
//     ll minimum = min(st[L][j], st[R - (1 << j) + 1][j]);
//     return minimum;
   
// }

//vll gf(ll n){
//     vll ans;
//     for(ll i=1;(i*i)<=n;i++){
//         if(n%i==0){
//             if(n/i == i)ans.pb(i);
//             else{ ans.pb(i); ans.pb(n/i);}
//         }
//     }
//     sort(all(ans));
//     return ans;
// }

// ll etf(ll n){

//     ll ans=n;

//     for(ll i=2;(i*i)<=n;i++){
//         if(n%i==0){
//             while(n%i==0)n/=i;
//             ans-= (ans/i);
//         }
//     }
//     if(n>1){
//         ans-=(ans/n);
//     }
//     return ans;
// }

ll n,m;
vvll g;

void solve()
{
	cin>>n>>m;
	g=vvll(n+1);
	for(ll i=0;i<m;i++){
		ll a,b;cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	ll ans=1e16;
	for(ll i=1;i<=n;i++){
		queue<ii>q;
		q.push({0LL,i});
		vll dis(n+1,1e16);
		dis[i]=0;
		while(!q.empty()){
			auto [d,node]= q.front();
			q.pop();
			for(auto it:g[node]){
				if(dis[it]==1e16){
					dis[it] = d+1;
					q.push({dis[it],it});
				}else if(dis[it]>=d){
					ans = min(ans, 1+dis[it]+d);
				}
			}
		}
	}
	if(ans==1e16){
		cout<<"-1\n";return;
	}
	cout<<ans<<endl;
}
signed main()
{
	IOS
	// int t;cin>>t;
	// while(t--)
	{
		solve();
	}
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45