oj.uz

Submission #448559

# Submission time Handle Problem Language Result Execution time Memory
448559 2021-07-30T17:37:45 Z BT21tata KOVANICE (COI15_kovanice) C++17
0 / 100
 226 ms 28300 KB 
#include<bits/stdc++.h>
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
#define SPEED ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define rall(v) (v).rbegin(),(v).rend()
#define all(v) (v).begin(),(v).end()
#define OK cerr<<"OK"<<endl<<flush
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define F first
#define S second
#define y0 jahdakdh
#define y1 jahsadakdakdh
#define endl '\n'
using namespace std;
const ll MOD=1e9+7;
// mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
 
int n, m, k, a[300005], dis[300005], mx, p[300005];
vector<int>g[300005], eq[300005];
bool used[300005], visited[300005];

void dfs(int v)
{
    visited[v]=1;
    for(int u : g[v])
    {
        if(!visited[u])
        {
            p[u]=v;
            dis[u]=dis[v]+1;
            if(dis[u]>dis[mx]) mx=u;
            dfs(u);
        }
    }
}

void equals(int v)
{
    for(int u : eq[v])
        if(!a[u]) a[u]=a[v], equals(u);
}

void path(int v, int x)
{
    if(!x) return;
    a[v]=x;
    equals(v);
    path(p[v], x-1);
}

int main()
{
    SPEED;
    cin>>n>>m>>k;
    while(k--)
    {
        int x, y; char q;
        cin>>x>>q>>y;
        if(q=='=')
        {
            eq[x].pb(y);
            eq[y].pb(x);
        }
        else
        {
            g[x].pb(y);
            used[y]=1;
        }
    }
    for(int i=1; i<=m; i++)
    {
        if(!used[i])
        {
            dis[i]=1; mx=i; p[i]=i;
            dfs(i);
            //cout<<mx<<' '<<dis[mx]<<endl;
            if(dis[mx]==n)
            {
                path(mx, n);
            }
        }
    }
    for(int i=1; i<=m; i++)
    {
        if(!a[i]) cout<<'?'<<endl;
        else cout<<'K'<<a[i]<<endl;
    }
    return 0;
}
/*
    3 5 3
    1<2
    2<4
    3=5
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 22064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 15832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 28300 KB Output isn't correct
2 Halted 0 ms 0 KB -