Submission #784751

#	Time	Username	Problem	Language	Result	Execution time	Memory
784751		BidoTeima	KOVANICE (COI15_kovanice)	C++17	10 / 100	103 ms	28776 KiB

kovanice

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