oj.uz

Submission #306591

# Submission time Handle Problem Language Result Execution time Memory
306591 2020-09-25T23:57:24 Z Marlov KOVANICE (COI15_kovanice) C++14
100 / 100
 604 ms 40208 KB 
/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#define maxN 300005
#define INF 1000000000

int N,M,V;
int p[maxN];
int r[maxN];
vector< pair<int,int> > grps;

//graphs
vector<int> ls,gs;
vector<int> adjl[maxN];
vector<int> adjg[maxN];
//dp
int dpmin[maxN];
int dpmax[maxN];



int findP(int n){
    if(n==p[n]) return n;
    int pn=findP(p[n]);
    p[n]=pn;
    return pn;
}

void combine(int a,int b){
    int p1=findP(a);
    int p2=findP(b);
    if(r[p1]<r[p2]) swap(p1,p2);
    p[p2]=p1;
    r[p1]=max(r[p1],r[p2]+1);
}   

void dfsmin(int n){
    if(dpmin[n]!=0) return;
    if(adjg[n].size()==0){
        dpmin[n]=1;
        return;
    }
    for(int a:adjg[n]){
        dfsmin(a);
        dpmin[n]=max(dpmin[n],dpmin[a]+1);
    }
}

void dfsmax(int n){
    if(dpmax[n]!=INF) return;
    if(adjl[n].size()==0){
        dpmax[n]=N;
        return;
    }
    for(int a:adjl[n]){
        dfsmax(a);
        dpmax[n]=min(dpmax[n],dpmax[a]-1);
    }
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N>>M>>V;
    cin.ignore();
    for(int i=0;i<M;i++){
        p[i]=i;
        r[i]=1;
        dpmin[i]=0;
        dpmax[i]=INF;
    }
    string str;
    for(int i=0;i<V;i++){
        getline(cin,str);
        stringstream sin(str);
        int f,s;
        char c;
        sin>>f>>c>>s;
        f--;
        s--;
        if(c=='='){
            combine(f,s);
        }else if(c=='<'){
            grps.push_back(make_pair(f,s));
        }
    }
    for(int i=0;i<grps.size();i++){
        adjl[findP(grps[i].first)].push_back(findP(grps[i].second));
        adjg[findP(grps[i].second)].push_back(findP(grps[i].first));
    }
    //find starts
    for(int i=0;i<M;i++){
        if(p[i]==i&&adjg[i].size()==0) ls.push_back(i);
        if(p[i]==i&&adjl[i].size()==0) gs.push_back(i);
    }

    for(int i=0;i<M;i++){
        dfsmin(findP(i));
        dfsmax(findP(i));
    }
    for(int i=0;i<M;i++){
        //cout<<dpmin[findP(i)]<<" "<<dpmax[findP(i)]<<'\n';
        if(dpmin[findP(i)]==dpmax[findP(i)]){
            cout<<"K"<<dpmin[findP(i)]<<'\n';
        }else{
            cout<<"?"<<'\n';
        }
    }

    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:107:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i=0;i<grps.size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14464 KB Output is correct
2 Correct 13 ms 14592 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 23668 KB Output is correct
2 Correct 180 ms 23924 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 17148 KB Output is correct
2 Correct 95 ms 17280 KB Output is correct
3 Correct 94 ms 17136 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 33544 KB Output is correct
2 Correct 498 ms 34328 KB Output is correct
3 Correct 503 ms 34284 KB Output is correct
4 Correct 571 ms 38764 KB Output is correct
5 Correct 604 ms 40208 KB Output is correct