Submission #448559

#	Time	Username	Problem	Language	Result	Execution time	Memory
448559		BT21tata	KOVANICE (COI15_kovanice)	C++17	0 / 100	226 ms	28300 KiB

kovanice

#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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40