oj.uz

Submission #448449

# Submission time Handle Problem Language Result Execution time Memory
448449 2021-07-30T08:07:23 Z BT21tata KOVANICE (COI15_kovanice) C++17
50 / 100
 321 ms 23740 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], 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8524 KB Output is correct
2 Correct 5 ms 8524 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 14132 KB Output is correct
2 Correct 102 ms 14264 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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