oj.uz

Submission #784750

# Submission time Handle Problem Language Result Execution time Memory
784750 2023-07-16T13:28:28 Z BidoTeima KOVANICE (COI15_kovanice) C++17
50 / 100
 163 ms 40020 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>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]);
}
int 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23800 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 29884 KB Output is correct
2 Correct 60 ms 31404 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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