oj.uz

Submission #784756

# Submission time Handle Problem Language Result Execution time Memory
784756 2023-07-16T13:34:38 Z BidoTeima KOVANICE (COI15_kovanice) C++17
50 / 100
 204 ms 41256 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],sz[N];
int rec(int i){
    if(f[i]==i)return i;
    return f[i]=rec(f[i]);
}
void merge(int a, int b){
	a=rec(a),b=rec(b);
  	if(a == b)
    	return;
  if(sz[a]<sz[b])
    swap(a,b);
  f[b]=a;
  sz[a]+=sz[b];
}
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;
      	sz[i]=1;
    }
    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){
            merge(a,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 14 ms 23764 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 30648 KB Output is correct
2 Correct 60 ms 30900 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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