oj.uz

Submission #306109

# Submission time Handle Problem Language Result Execution time Memory
306109 2020-09-24T14:20:58 Z Marlov KOVANICE (COI15_kovanice) C++14
50 / 100
 852 ms 30160 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,int l){
    if(l<dpmin[n]){
        dpmin[n]=l;
        for(int i:adjl[n]){
            dfsmin(i,l+1);
        }
    }
}

void dfsmax(int n,int g){
    if(g>dpmax[n]){
        dpmax[n]=g;
        for(int i:adjg[n]){
        dfsmax(i,g-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]=INF;
        dpmax[i]=0;
    }
    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<ls.size();i++){
        dfsmin(ls[i],1);
    }
    for(int i=0;i<gs.size();i++){
        dfsmax(gs[i],N);
    }
    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:101: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]
  101 |     for(int i=0;i<grps.size();i++){
      |                 ~^~~~~~~~~~~~
kovanice.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=0;i<ls.size();i++){
      |                 ~^~~~~~~~~~
kovanice.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i=0;i<gs.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 22480 KB Output is correct
2 Correct 197 ms 22640 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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