oj.uz

Submission #80068

# Submission time Handle Problem Language Result Execution time Memory
80068 2018-10-18T16:24:54 Z fabjanm KOVANICE (COI15_kovanice) C++
0 / 100
 2000 ms 16648 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<iomanip>
#include<cstring>

using namespace std;

int n,m,v;
int brcv=0;

vector<pair<int,int> >jed;
vector<pair<pair<int,int>,char> >raz;

int mapa[300050];

int parent[300500];
vector<int> sus[300500];

int sol[300500];
vector<int>koji;

void input(){
    cin>>n>>m>>v;
    int br1,br2;
    char zn;
    string r;

    for(int i=0;i<v;i++){
        cin>>br1>>zn>>br2;
        if(zn=='=')jed.push_back(make_pair(min(br1,br2),max(br1,br2)));
        else raz.push_back(make_pair(make_pair(br1,br2),zn));
    }
}

int rek(int cvor, int br){
    if(br==n){
        sol[cvor]=1;
        return 1;
    }
    else if(sus[cvor].size()==0)return 0;
    bool soll=0;
    for(int i=0;i<sus[cvor].size();i++) soll=soll || rek(sus[cvor][i], br+1);
    if(soll) sol[cvor]=n-br+1;
    return soll;
}

void solve(){
    sort(jed.begin(),jed.end());
    int oz=0;
    for(int i=0;i<jed.size();i++){
        int br1=jed[i].first;
        int br2=jed[i].second;
        if(mapa[br1]==0 && mapa[br2]==0){
            oz++;
            brcv++;
            mapa[br1]=oz;
            mapa[br2]=oz;
        }
        else if(mapa[br1]==0 && mapa[br2]!=0)mapa[br1]=mapa[br2];
        else if(mapa[br1]!=0 && mapa[br2]==0)mapa[br2]=mapa[br1];
    }

    for(int i=0;i<raz.size();i++){
        int br1=raz[i].first.first;
        int br2=raz[i].first.second;
        char zn=raz[i].second;

        if(mapa[br1]==0){
            oz++;
            brcv++;
            mapa[br1]=oz;
        }
        if(mapa[br2]==0){
            oz++;
            brcv++;
            mapa[br2]=oz;
        }

        if(zn=='<'){
            parent[mapa[br1]]=mapa[br2];
            sus[mapa[br2]].push_back(mapa[br1]);
        }
        else{
            parent[mapa[br2]]=mapa[br1];
            sus[mapa[br1]].push_back(mapa[br2]);
        }
    }

    /*for(int i=1;i<=brcv;i++)cout<<i<<" -> "<<parent[i]<<endl;
    cout<<endl<<endl;

    for(int i=1;i<=brcv;i++){
        cout<<i<<" -> ";
        for(int j=0;j<sus[i].size();j++){
            cout<<sus[i][j]<<" ";
        }
        cout<<endl;
    }*/

    for(int i=1;i<=brcv;i++){
        int cvor=i;
        //cout<<cvor<<"    "<<parent[cvor]<<endl;
        if(parent[cvor]==0){
            //cout<<cvor<<endl;
            rek(cvor, 1);
        }
    }

    /*cout<<"size od koji je :   "<<koji.size()<<endl;
    for(int i=0;i<koji.size();i++){
        int br=1,cvor=koji[i];
        for(int j=0;j<n;j++){
            if(sol[cvor]!=0)break;
            sol[cvor]=br;
            cvor=parent[cvor];
            br++;
        }
    }*/

    ///for(int i=1;i<=m;i++)cout<<i<<" -> "<<mapa[i]<<endl;
    ///cout<<endl<<endl;
    ///for(int i=1;i<=brcv;i++)cout<<i<<" -> "<<parent[i]<<endl;
    //cout<<brcv<<endl;
}

void print(){
    for(int i=1;i<=m;i++){
        if(sol[mapa[i]] != 0)cout<<"K"<<sol[mapa[i]]<<endl;
        else cout<<"?"<<endl;
    }
}

int main(){
    input();
    solve();
    print();



    return 0;
}

Compilation message

kovanice.cpp: In function 'int rek(int, int)':
kovanice.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<sus[cvor].size();i++) soll=soll || rek(sus[cvor][i], br+1);
                 ~^~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'void solve()':
kovanice.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<jed.size();i++){
                 ~^~~~~~~~~~~
kovanice.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<raz.size();i++){
                 ~^~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 11784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 16648 KB Time limit exceeded
2 Halted 0 ms 0 KB -