| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 224401 | 2020-04-17T18:55:38 Z | PedroBigMan | Birmingham (COCI20_birmingham) | C++14 | 169 ms | 21872 KB |
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
ll sqr(ll x)
{
ll hi=x; ll lo=0LL;
while(hi>lo)
{
ll mid=(lo+hi+1)/2LL;
if(mid*mid<=x) {lo=mid;}
else {hi=mid-1LL;}
}
return hi;
}
class Graph
{
public:
ll N;
vector<vector<ll> > adj;
vector<bool> visited; //for DFS/BFS
Graph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
}
vector<ll> BFS(ll s)
{
vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
REP(i,0,N) {visited[i]=false;}
distance[s]=0; visited[s]=true;
deque<ll> d; d.pb(s); ll cur;
while(!d.empty())
{
cur=d.front(); d.pop_front();
REP(i,0,adj[cur].size())
{
if(!visited[adj[cur][i]])
{
visited[adj[cur][i]]=true;
d.pb(adj[cur][i]);
distance[adj[cur][i]]=distance[cur]+1;
}
}
}
return distance;
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll N,M,Q,K; cin>>N>>M>>Q>>K;
vector<ll> q; In(q,Q); REP(i,0,Q) {q[i]--;}
vector<ll> xx; vector<vector<ll> > adj; REP(i,0,N) {adj.pb(xx);}
pl cur;
REP(i,0,M)
{
cin>>cur.ff>>cur.ss; cur.ff--; cur.ss--;
adj[cur.ff].pb(cur.ss); adj[cur.ss].pb(cur.ff);
}
REP(i,1,q.size())
{
REP(j,0,adj[q[i]].size()) {adj[q[0]].pb(adj[q[i]][j]);}
}
Graph G(adj);
vector<ll> d=G.BFS(q[0]);
vector<ll> ans; REP(i,0,N) {ans.pb(0LL);}
REP(i,0,N)
{
ans[i]=sqr(K*K+8LL*K*d[i]);
ans[i]+=(K-1LL);
ans[i]/=(2LL*K);
}
REP(i,0,q.size()) {ans[q[i]]=0LL;}
REP(i,0,N) {cout<<ans[i]<<" ";}
cout<<endl;
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 5 ms | 384 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 384 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 5 ms | 384 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 5 ms | 384 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 6 ms | 384 KB | Output is correct |
| 2 | Correct | 5 ms | 384 KB | Output is correct |
| 3 | Correct | 5 ms | 384 KB | Output is correct |
| 4 | Correct | 5 ms | 384 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 384 KB | Output is correct |
| 2 | Correct | 4 ms | 384 KB | Output is correct |
| 3 | Correct | 5 ms | 384 KB | Output is correct |
| 4 | Correct | 5 ms | 384 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 384 KB | Output is correct |
| 2 | Correct | 6 ms | 512 KB | Output is correct |
| 3 | Correct | 5 ms | 384 KB | Output is correct |
| 4 | Correct | 5 ms | 384 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 160 ms | 20832 KB | Output is correct |
| 2 | Incorrect | 140 ms | 21648 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 163 ms | 21672 KB | Output is correct |
| 2 | Incorrect | 151 ms | 21476 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 137 ms | 21092 KB | Output is correct |
| 2 | Incorrect | 158 ms | 21872 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 164 ms | 20220 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 167 ms | 20196 KB | Output is correct |
| 2 | Incorrect | 142 ms | 20912 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 169 ms | 20324 KB | Output is correct |
| 2 | Incorrect | 135 ms | 20960 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 153 ms | 20580 KB | Output is correct |
| 2 | Incorrect | 113 ms | 19940 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |