Submission #784760

#	Time	Username	Problem	Language	Result	Execution time	Memory
784760		BidoTeima	KOVANICE (COI15_kovanice)	C++17	50 / 100	244 ms	46356 KiB

kovanice

#include <bits/stdc++.h>
using namespace std; 
using ll = int64_t;
#define int int64_t
const int N = 3e5 + 3;
bool used=0;
set<int>st;
vector<int>adj1[N],adj2[N],temp[N];
bool ok = 1;
int dp1[N],dp2[N];
int dfs1(int node){
    if(dp1[node]!=-1)
        return dp1[node];
    int ret = 1;
    for(int child : adj1[node]){
        ret=max(ret, dfs1(child) + 1);
    }
    return dp1[node]=ret;
}
int dfs2(int node){
    if(dp2[node]!=-1)
        return dp2[node];
    int ret = 1;
    for(int child:adj2[node]){
        ret=max(ret, dfs2(child) + 1);
    }
    return dp2[node]=ret;
} 
int f[N];
int rec(int i){
    if(f[i]==i)return i;
    return f[i]=rec(f[i]);
}
int32_t main()
{ 
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m,v;
    cin>>n>>m>>v;
    memset(dp1,-1,sizeof(dp1));
    memset(dp2,-1,sizeof(dp2));
    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);
        } 
    }
    for(int i = 1; i <= m; i++)rec(i);
    for(int i = 1; i <= m; i++){
        for(int child : temp[i]){
            adj1[f[i]].push_back(f[child]);
            adj2[f[child]].push_back(f[i]); 
        }
    }
    for(int i = 1; i <= n; i++){
        st.insert(i);
    }
    vector<int>vec;
    for(int i = 1; i <= m; i++){
        if(dfs1(f[i])+dfs2(f[i]) != n+1){
            vec.push_back('?');
        }
        else vec.push_back(dfs1(f[i]));
    }  
    for(int i : vec){
        if(i == '?')cout<<"?\n";
        else cout<<'K'<<i<<'\n';
    }
    return 0;
}

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