Submission #238539

# Submission time Handle Problem Language Result Execution time Memory
238539 2020-06-11T16:56:56 Z Salito Birmingham (COCI20_birmingham) C++14
0 / 70
260 ms 14200 KB
#include<bits/stdc++.h>
using namespace std;
int const maxn = 100005;

int n,m,q,k;
int a[maxn];
vector<int>v[maxn];

void read()
{
    int i;
	cin>>n>>m>>q>>k;

	for(i=0;i<q;i++)
        cin>>a[i];

    int x,y;
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

int ans[maxn];
queue<int>gq;
bool used[maxn],used2[maxn];
void dfs(int i, int d, int p)
{
    if(d == 0)return ;
    used2[i]=true;
    int j,sz=v[i].size();
    for(j=0;j<sz;j++)
    {
        int nb = v[i][j];
        if(!used2[nb])
        {
            //cout<<" "<<nb<<endl;
            if(!ans[nb])
            {
                gq.push(nb);
                ans[nb] = ans[p] + 1;
            }
            else ans[nb] = min(ans[nb],ans[p]+1);
            dfs(nb,d-1,p);
        }
    }
}

void bfs_solve()
{
    int i;
    for(i=0;i<q;i++)
    {
        gq.push(a[i]);
        ans[a[i]] = 1;
        used[a[i]]=true;
    }

    while(!gq.empty())
    {
        int t = gq.front();
        gq.pop();
        //cout<<t<<" "<<endl;
        copy(used2,used+1,used+n+1);
        dfs(t,k*ans[t],t);
        used[t]=true;

    }
}

void print()
{
    int i;
    for(i=1;i<=n;i++)
        cout<<ans[i]-1<<" ";
    cout<<endl;
}

int main()
{
    read();

    bfs_solve();

    print();
	return 0;
}
/*

6 5  1
1
1 2
2 3
3 5
5 4
4 6
*/
# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 219 ms 13664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 221 ms 14200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 7148 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 185 ms 13392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 7008 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 7068 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 13560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -