제출 #306105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306105		Marlov	KOVANICE (COI15_kovanice)	C++14	0 / 100	2089 ms	36340 KiB

kovanice

/*
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=='<'){
            cout<<f<<" "<<s<<'\n';
            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
*/

컴파일 시 표준 에러 (stderr) 메시지

kovanice.cpp: In function 'int main()':
kovanice.cpp:102: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]
  102 |     for(int i=0;i<grps.size();i++){
      |                 ~^~~~~~~~~~~~
kovanice.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i=0;i<ls.size();i++){
      |                 ~^~~~~~~~~~
kovanice.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i=0;i<gs.size();i++){
      |                 ~^~~~~~~~~~

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