oj.uz

Submission #37934

# Submission time Handle Problem Language Result Execution time Memory
37934 2017-12-29T09:13:58 Z patrikpavic2 KOVANICE (COI15_kovanice) C++14
100 / 100
 536 ms 40928 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

#define X first
#define Y second

using namespace std;

typedef long long int llint;
typedef pair < int,int> pii;

const int N = 3e5 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

vector < int > g[N];
vector < int > r[N];
vector < pii > edg;
vector < int > vv;

queue < int > q;

int n,m,v;
int col[N],wh[N],par[N],dp[N][2],in[N];
int x,y;
char c;

int pr(int x){
    return par[x] = ((x == par[x]) ? (x) : (pr(par[x])));
}

void mrg(int x,int y){
    par[pr(x)] = pr(y);
}

int main(){
    scanf("%d%d%d",&n,&m,&v);
    for(int i = 1;i<=m;i++)
        par[i] = i;
    for(int i = 0;i<v;i++){
        scanf("%d%c%d",&x,&c,&y);
        if(c == '=') mrg(x,y);
        if(c == '<') edg.push_back(make_pair(x,y));
        if(c == '>') edg.push_back(make_pair(y,x));
    }
    for(int i = 0;i<edg.size();i++){
        g[pr(edg[i].X)].push_back(pr(edg[i].Y));
        r[pr(edg[i].Y)].push_back(pr(edg[i].X));
    }
    for(int i = 1;i<=m;i++){
        if(!g[i].size() && !r[i].size()) continue;
        sort(g[i].begin(),g[i].end());
        g[i].erase(unique(g[i].begin(),g[i].end()),g[i].end());
        sort(r[i].begin(),r[i].end());
        r[i].erase(unique(r[i].begin(),r[i].end()),r[i].end());
        if(!r[i].size()) q.push(i);
        in[i] = r[i].size();
    }
    while(!q.empty()){
        int x = q.front();q.pop();
        vv.push_back(x);
        for(int i = 0;i<g[x].size();i++){
            in[g[x][i]]--;
            if(!in[g[x][i]])
                q.push(g[x][i]);
        }
    }
    for(int i = 0;i<vv.size();i++){
        int x = vv[i];
        dp[x][0] = 0;
        for(int j = 0;j<r[x].size();j++){
            dp[x][0] = max(dp[x][0], dp[r[x][j]][0] + 1);
        }
    }
    for(int i = vv.size() - 1;i>=0;i--){
        int x = vv[i];
        dp[x][1] = 0;
        for(int j = 0;j<g[x].size();j++){
            dp[x][1] = max(dp[x][1], dp[g[x][j]][1] + 1);
        }
    }
    for(int i = 1;i<=m;i++){
        int rl = pr(i);
        if(dp[rl][0] + dp[rl][1] == n - 1) printf("K%d\n",dp[rl][0] + 1);
        else printf("?\n");
    }
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<edg.size();i++){
                    ^
kovanice.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<g[x].size();i++){
                        ^
kovanice.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<vv.size();i++){
                    ^
kovanice.cpp:73:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<r[x].size();j++){
                        ^
kovanice.cpp:80:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<g[x].size();j++){
                        ^
kovanice.cpp:39:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&v);
                             ^
kovanice.cpp:43:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%c%d",&x,&c,&y);
                                 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23060 KB Output is correct
2 Correct 0 ms 23060 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 27368 KB Output is correct
2 Correct 129 ms 27552 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 25228 KB Output is correct
2 Correct 36 ms 25220 KB Output is correct
3 Correct 56 ms 25220 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 34684 KB Output is correct
2 Correct 423 ms 34568 KB Output is correct
3 Correct 446 ms 34548 KB Output is correct
4 Correct 519 ms 40884 KB Output is correct
5 Correct 536 ms 40928 KB Output is correct