Submission #448449

#	Time	Username	Problem	Language	Result	Execution time	Memory
448449		BT21tata	KOVANICE (COI15_kovanice)	C++17	50 / 100	321 ms	23740 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], def, mn, mx, ans[300005];
vector<pii>g[300005];
bool used[300005];
 
void dfs(int v)
{
    used[v]=1;
    mx=max(mx, a[v]);
    mn=min(mn, a[v]);
    for(pii u : g[v])
    {
        if(!used[u.F])
        {
            a[u.F]=a[v]+u.S;
            dfs(u.F);
        }
    }
}
 
void dfs(int v, int dif)
{
    ans[v]=a[v]+dif;
    for(pii u : g[v])
    {
        if(!ans[u.F]) dfs(u.F, dif);
    }
}
 
int main()
{
    SPEED;
    memset(a, 127, sizeof(a));
    def=a[0];
    cin>>n>>m>>k;
    while(k--)
    {
        int x, y; char q;
        cin>>x>>q>>y;
        if(q=='=')
        {
            g[x].pb({y, 0});
            g[y].pb({x, 0});
        }
        else
        {
            g[x].pb({y, 1});
            g[y].pb({x, -1});
        }
    }
    for(int i=1; i<=m; i++)
    {
        if(!used[i])
        {
            mx=mn=1; a[i]=1;
            dfs(i);
            if(mx-mn+1==n)
            {
                dfs(i, n-mx);
            }
        }
    }
    for(int i=1; i<=m; i++)
    {
        if(!ans[i]) cout<<'?'<<endl;
        else cout<<'K'<<ans[i]<<endl;
    }
    return 0;
}
/*
    0 -> '='
    1 -> '<'
   -1 -> '>'
*/

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40