oj.uz

Submission #976339

# Submission time Handle Problem Language Result Execution time Memory
976339 2024-05-06T12:48:43 Z Error404 Love Polygon (BOI18_polygon) C++17
50 / 100
 356 ms 27236 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define pi pair<int,int>
 
const int MAX = 2e5; 
    
    
int n;
map<string,int>m;
vector<int>g[MAX];
int love[MAX];
int indegree[MAX];
int visited[MAX];
 map<int,string>name;
int main(){
    int n;
    cin>> n;
    string  from, to;
    int k = 1;
    if(n%2){
        cout << -1 << endl;
        return 0;
    }
    int a,b;
    for(int i = 0; i < n; i++){
        cin >> from >> to;
    
        if(m[from]==0) {
           // cout << from << " " << k << endl;
            name[k]=from;
            m[from]=k++;
           
        }
        if(m[to]==0){
           // cout << to << " " << k << endl;
           name[k]=to;
            m[to]=k++;
            
        } 
        a = m[from], b= m[to];
        love[a]=b;
        if(love[b]==a && a!=b){
            visited[a]= visited[b]=1;
        }
        else{
            g[a].pb(b);
            indegree[b]++;
        }
    }
    
    
    priority_queue<pi,vector<pi>, greater<pi>>q;
    for(int i = 1; i <= n; i++){
        if(indegree[i]==0 && visited[i]==0){
            q.push({0,i});
        }
    }
    ll ans = 0;
    while(!q.empty()){
        int from = q.top().s;
        q.pop();
       //cout <<  name[from] << " " << ans<< endl;
        for(int to : g[from]){
            indegree[to]--;
            if(!visited[to]&&!visited[from]){
                if(visited[from])continue;
                q.push({indegree[to],to});
                
                love[from]=to;
                ans++;
                visited[from]= visited[to] =1;
                
            }
            else if(indegree[to]==0 && !visited[to]){
                q.push({0,to});
            }
        }
    }
    
    // ans /=2;
     
     
     ll comp= 0;
     for(int i = 1; i <= n; i++){
         if(!visited[i] &&!visited[love[i]]&& love[i]!=i && love[i]!=0) {
             while(!visited[i]){
                 visited[i]=1;
                 i =love[i];
                 comp++;
             }
             ans += (comp+1)/2;
         }
     }
     for(int i = 1; i <= n; i++){
         if(!visited[i]) {
             ans++;
            
         }
     }
     
     cout << ans << endl;
     
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 3 ms 7260 KB Output is correct
9 Correct 2 ms 7088 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7320 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7316 KB Output is correct
14 Correct 3 ms 7256 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Incorrect 233 ms 26188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 26436 KB Output is correct
2 Correct 271 ms 26548 KB Output is correct
3 Correct 237 ms 26024 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 330 ms 26156 KB Output is correct
6 Correct 356 ms 26688 KB Output is correct
7 Correct 317 ms 26684 KB Output is correct
8 Correct 266 ms 26592 KB Output is correct
9 Correct 242 ms 27024 KB Output is correct
10 Correct 230 ms 27236 KB Output is correct
11 Correct 2 ms 7260 KB Output is correct
12 Correct 2 ms 7284 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 3 ms 7260 KB Output is correct
9 Correct 2 ms 7088 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7320 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7316 KB Output is correct
14 Correct 3 ms 7256 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct
16 Correct 2 ms 7260 KB Output is correct
17 Correct 2 ms 7260 KB Output is correct
18 Correct 2 ms 7260 KB Output is correct
19 Incorrect 233 ms 26188 KB Output isn't correct
20 Halted 0 ms 0 KB -