oj.uz

Submission #392098

# Submission time Handle Problem Language Result Execution time Memory
392098 2021-04-20T13:44:44 Z sad Birmingham (COCI20_birmingham) C++14
70 / 70
 225 ms 11632 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n,m,k,qq;
const int N=100090;
vector<int>v[N];
queue<pair<int,int>>q;
int dis[N],vis[N];
int ch(ll c,ll ds)
{
    c*=(c+1);c/=2;
    c*=k;
    if(c>ds)return 0;
    return 1;
}
int main()
{
    cin>>n>>m>>qq>>k;
    for(int i=0;i<qq;i++)
    {
        int x;cin>>x;q.push({x,0});
    }
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    while(!q.empty())
    {
        pair<int,int>x=q.front();
        q.pop();
        if(vis[x.fi])continue;
        vis[x.fi]=1;
        dis[x.fi]=x.se;
        for(auto it:v[x.fi])
        {
            if(vis[it])continue;
            q.push({it,x.se+1});
        }
    }
    for(int i=1;i<n+1;i++)
    {

        int st=0,en=100090;
        while(st<en)
        {
            int mid=(st+en)/2;
            if(ch(mid,dis[i]))
                st=mid+1;
            else en=mid;
        }
        st--;
        ll c=(st)*(st+1);
        c/=2;
        c*=k;
        if(dis[i]>c)st++;
        cout<<st<<" ";
    }


}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2664 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 10184 KB Output is correct
2 Correct 192 ms 10644 KB Output is correct
3 Correct 213 ms 11504 KB Output is correct
4 Correct 160 ms 9484 KB Output is correct
5 Correct 148 ms 9796 KB Output is correct
6 Correct 200 ms 11632 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 10608 KB Output is correct
2 Correct 199 ms 10388 KB Output is correct
3 Correct 215 ms 10924 KB Output is correct
4 Correct 197 ms 10860 KB Output is correct
5 Correct 180 ms 10388 KB Output is correct
6 Correct 179 ms 10528 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 10336 KB Output is correct
2 Correct 193 ms 10796 KB Output is correct
3 Correct 195 ms 11364 KB Output is correct
4 Correct 208 ms 10736 KB Output is correct
5 Correct 204 ms 9924 KB Output is correct
6 Correct 181 ms 10596 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 9852 KB Output is correct
2 Correct 168 ms 10416 KB Output is correct
3 Correct 189 ms 10928 KB Output is correct
4 Correct 177 ms 10116 KB Output is correct
5 Correct 161 ms 9644 KB Output is correct
6 Correct 177 ms 10536 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 9908 KB Output is correct
2 Correct 225 ms 10076 KB Output is correct
3 Correct 167 ms 10352 KB Output is correct
4 Correct 165 ms 10052 KB Output is correct
5 Correct 181 ms 10132 KB Output is correct
6 Correct 189 ms 10404 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 9828 KB Output is correct
2 Correct 169 ms 10124 KB Output is correct
3 Correct 174 ms 10396 KB Output is correct
4 Correct 170 ms 10416 KB Output is correct
5 Correct 188 ms 10060 KB Output is correct
6 Correct 166 ms 10648 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 10024 KB Output is correct
2 Correct 181 ms 9572 KB Output is correct
3 Correct 221 ms 11140 KB Output is correct
4 Correct 173 ms 9876 KB Output is correct
5 Correct 175 ms 10256 KB Output is correct
6 Correct 214 ms 11548 KB Output is correct