oj.uz

Submission #784751

# Submission time Handle Problem Language Result Execution time Memory
784751 2023-07-16T13:29:28 Z BidoTeima KOVANICE (COI15_kovanice) C++17
10 / 100
 103 ms 28776 KB 
#include <bits/stdc++.h>
using namespace std; 
using ll = int64_t;
const int N = 3e5 + 3;
bool used=0;
set<int>st;
vector<int>adj[N],temp[N];
bool ok = 1;
int dp[N];
int dfs(int node){
    if(dp[node] != -1){
        return dp[node];
    } 
    if(adj[node].empty() && used==0){
        st.erase(st.find(1));
        used = 1;
        return dp[node]=1;
    }
    else if(adj[node].empty()){
        return dp[node]=0;
    }
    int mx = 0;
    for(int child : adj[node]){
        int res = dfs(child);
        if(!res){
            return dp[node]=0;
        }
        mx = max(mx, res);
    }
    auto it = st.upper_bound(mx);
    if(it == st.end()){
        ok=0;
        return dp[node]=0;
    }
    int val = *it;
    st.erase(it);
    return dp[node] = val;
}
int f[N];
int rec(int i){
    if(f[i]==i)return i;
    return f[i]=rec(f[i]);
}
int main()
{ 
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m,v;
    cin>>n>>m>>v;
    memset(dp,-1,sizeof(dp));
    for(int i = 1; i <= m; i++){
        f[i]=i;
    }
    for(int i = 0; i < v; i++){
        string s;
        cin>>s;
        int j = 0;
        int a = 0, b = 0;
        bool l = 0, eq = 0;
        while(j != int(s.size())){
            if(s[j]=='<'){
                l=1;
                ++j;
                continue;
            }
            if(s[j] == '='){
                eq = 1,l=1;
                ++j;
                continue;
            }
            if(!l)a*=10,a+=s[j]-'0';
            else b*=10,b+=s[j]-'0';;
            ++j;
        }
        if(eq){
            f[rec(a)]=f[rec(b)];
        }
        else{
            temp[b].push_back(a);
        } 
    }
    int hasparent[m+1]{};
    for(int i = 1; i <= m; i++)rec(i);
    for(int i = 1; i <= m; i++){
        for(int child : temp[i]){
            adj[f[i]].push_back(f[child]);
            hasparent[f[child]]=1;
        }
    }
    for(int i = 1; i <= n; i++){
        st.insert(i);
    }
    vector<int>vec;
    for(int i = 1; i <= m; i++){
        vec.push_back(dfs(f[i]));
    }  
    for(int i : vec){
        if(i == 0)cout<<"?\n";
        else cout<<'K'<<i<<'\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16724 KB Output is correct
2 Correct 21 ms 17552 KB Output is correct
3 Correct 16 ms 17388 KB Output is correct

Subtask #4
0 / 40.0

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